`
bmqnc
  • 浏览: 127626 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

srm 237 Div2 1000 pts

J# 
阅读更多

这题的500pts顺便提一下,500的纯暴力是不行的,这题主要用到了集合论的知识,一个元素和两个元素的都好做,三个元素的并集我倒忘记了公式,后来还查了一下关于三个集合的并集知识。

这题不是一般的恶心,关键是题意不明确,我是看了好久才看懂讲了什么意思。。。。
代码如下:
// Paste me into the FileEdit configuration dialog
import java.io.*;
import java.util.*;
import java.util.regex.*;
//srm 237 Div2 1000 pts

public class MirrorPath {
   public String[] path(String[] map) {
//	   	for(String s:map)
//	   		System.out.println(s);
		int row=map.length;
		int col=map[0].length();
//		System.out.println(row+" "+col);
		String[] ans=new String[row];
		char[][] chs=new char[row][col];
		Pos[] step=new Pos[4];
		step[0]=new Pos(1,0);
		step[1]=new Pos(0,-1);
		step[2]=new Pos(-1,0);
		step[3]=new Pos(0,1);
		Pos start=null;
		Pos end=null;
		for(int i=0;i<row;i++){
			chs[i]=map[i].toCharArray();
			for(int j=0;j<col;j++){
				if(chs[i][j]=='.'){
					if(start==null&&(i==0||i==row-1||j==0||j==col-1)){
						start=new Pos();
						start.x=i;
						start.y=j;
						makeDir(start,i,j,row,col);
					}else if(end==null&&(i==0||i==row-1||j==0||j==col-1)){
						end=new Pos();
						end.x=i;
						end.y=j;
					}	
				}
			}//for
		}//for
		
		LinkedList<Path> ll=new LinkedList<Path>();
		LinkedList<Path> all=new LinkedList<Path>();
		Path init=new Path(start);
		init.mirCor.add(start.x+" "+start.y+" "+start.dir);
		ll.add(init);
		while(ll.size()>0){
				Path path=ll.remove();
				Pos pos=path.ll.getLast();
				int nx=pos.x+step[pos.dir].x;
				int ny=pos.y+step[pos.dir].y;
				if(nx==end.x&&ny==end.y){
					path.ll.add(new Pos(nx,ny,pos.dir));
					all.add(path);
				}else if(nx>=0&&nx<row&&ny>=0&&ny<col){
						if(chs[nx][ny]=='/'||chs[nx][ny]=='`'){
							Path[] paths=makePath(path,pos,nx,ny,chs);
							for(Path p:paths){
								String mirCor=nx+" "+ny+" "+p.ll.getLast().dir;
								String mirCor2=nx+" "+ny+" "+(p.ll.getLast().dir+2)%4;
								if(!p.mirCor.contains(mirCor)&&!p.mirCor.contains(mirCor2)){
									ll.add(p);
									p.mirCor.add(mirCor);
								}
							}
						}else{
							String mirCor=nx+" "+ny+" "+pos.dir;
							String mirCor2=nx+" "+ny+" "+(pos.dir+2)%4;
							if(!path.mirCor.contains(mirCor)&&!path.mirCor.contains(mirCor2)){
								path.ll.add(new Pos(nx,ny,pos.dir));
								ll.add(path);
								path.mirCor.add(mirCor);
							}
						}//else
				}
		}//while
		
		for(Path p:all){
//			print(p,chs);
			for(Pos pos:p.ll){
				int x=pos.x;
				int y=pos.y;
				switch(chs[x][y]){
					case '.':
						if(pos.dir==0||pos.dir==2)
							chs[x][y]='|';
						else
							chs[x][y]='-';	
						break;
					case '|':
						if(pos.dir==1||pos.dir==3)
							chs[x][y]='+';
						 break;
					case '-':
						if(pos.dir==0||pos.dir==2)
							chs[x][y]='+';
						break;
					default:
						break;	
				}
			}//for
		}//for
		
		for(int i=0;i<row;i++){
			ans[i]=new String(chs[i]);
		}
		
		return ans;
   }
   
   private void print(Path path,char[][] chs) {
	   boolean printed=false;
	   for(Pos p:path.ll){
		   if(p.x==1&&p.y==44){
			   printed=true;
			   break;
		   }
	   }
	   
	   if(!printed)
		   	return;
	  
	   for(Pos p:path.ll){
		   System.out.println(p);
	   }
//	System.out.println("///////////////////////////////////////////////////");
//	   for(Pos p:path.ll)
//		   System.out.println(p);
//		   
//		   System.out.println("///////////////////////////////////////////////////");
//	   System.out.println();
	   System.exit(0);
	
}

public Path[] makePath(Path path,Pos pos,int nx,int ny,char[][] chs){
   	Vector<Path> vec=new Vector<Path>();
   		if(pos.dir==0||pos.dir==2){
   			//case 1
   			int dir=3;
   			Path p=new Path();
   			for(String s:path.mirCor.toArray(new String[0]))
   				p.mirCor.add(s);
			for(Pos p1:path.ll){
				p.ll.add(p1);
			}
			p.ll.add(new Pos(nx,ny,dir));
			vec.add(p);
   			
			//case 2
   			dir=1;
   			p=new Path();
   			for(String s:path.mirCor.toArray(new String[0]))
   				p.mirCor.add(s);
			for(Pos p1:path.ll){
				p.ll.add(p1);
			}
			p.ll.add(new Pos(nx,ny,dir));
			vec.add(p);
   		}else{
   			//case 1
   			int dir=0;
   			Path p=new Path();
   			for(String s:path.mirCor.toArray(new String[0]))
   				p.mirCor.add(s);
			for(Pos p1:path.ll){
				p.ll.add(p1);
			}
			p.ll.add(new Pos(nx,ny,dir));
			vec.add(p);
   			
   			//case 2
   			dir=2;
   			p=new Path();
   			for(String s:path.mirCor.toArray(new String[0]))
   				p.mirCor.add(s);
			for(Pos p1:path.ll){
				p.ll.add(p1);
			}
			p.ll.add(new Pos(nx,ny,dir));
   			vec.add(p);
   		}
   		
   		return vec.toArray(new Path[0]);
   }
   
  class Path{
  	LinkedList<Pos>	ll=new 	LinkedList<Pos>();
  	HashSet<String> mirCor=new HashSet<String>();
  	public Path(Pos cur){
  		ll.add(cur);
  	}
  	public Path(){}
  }
   
   public void makeDir(Pos pos,int i,int j,int row,int col){
	 	//clockwise
	   if(i==0)
	   	pos.dir=0;//from the top shine		
	   else if(i==row-1)
	   	pos.dir=2;//from the buttom
	   else if(j==0)
	   	pos.dir=3;//the left		
	   else if(j==col-1)
	   	pos.dir=1;//the right	
   }
   
   class Pos{
   	int x;
   	int y;	
   	int dir=-1;
   	
   	public Pos(){}
   	public Pos(int x,int y){
   		this.x=x;
   		this.y=y;
   	}
   	public Pos(int x,int y,int dir){
   		this(x,y);
   		this.dir=dir;	
   	}
  
   	public String toString() {
   		return x+" "+y+" "+dir;
   	}
   }


// BEGIN CUT HERE
   public static void main(String[] args) {
		if (args.length == 0) {
			MirrorPathHarness.run_test(-1);
		} else {
			for (int i=0; i<args.length; ++i)
				MirrorPathHarness.run_test(Integer.valueOf(args[i]));
		}
	}
// END CUT HERE
}

// BEGIN CUT HERE
class MirrorPathHarness {
	public static void run_test(int casenum) {
		if (casenum != -1) {
			if (runTestCase(casenum) == -1)
				System.err.println("Illegal input! Test case " + casenum + " does not exist.");
			return;
		}
		
		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = runTestCase(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if (total == 0) {
			System.err.println("No test cases run.");
		} else if (correct < total) {
			System.err.println("Some cases FAILED (passed " + correct + " of " + total + ").");
		} else {
			System.err.println("All " + total + " tests passed!");
		}
	}
	
	static boolean compareOutput(String[] expected, String[] result) { if (expected.length != result.length) return false; for (int i=0; i<expected.length; ++i) if (!expected[i].equals(result[i])) return false; return true; }

	static String formatResult(String[] res) {
		String ret = "";
		ret += "{";
		for (int i=0; i<res.length; ++i) {
			if (i > 0) ret += ",";
			ret += String.format(" \"%s\"", res[i]);
		}
		ret += " }";
		return ret;
	}
	
	static int verifyCase(int casenum, String[] expected, String[] received) { 
		System.err.print("Example " + casenum + "... ");
		if (compareOutput(expected, received)) {
			System.err.println("PASSED");
			return 1;
		} else {
			System.err.println("FAILED");
			System.err.println("    Expected: " + formatResult(expected)); 
			System.err.println("    Received: " + formatResult(received)); 
//			System.out.println("//////////////////////");
//			for(String s:expected)
//				System.out.println(s);
//			System.out.println("//////////////////////");	
//			
//			System.out.println("*********************");
//			for(String s:received)
//				System.out.println(s);
//			System.out.println("*********************");
			
			return 0;
		}
	}

	static int runTestCase(int casenum) {
		switch(casenum) {
//		case 0: {
//			String[] map              = { "#.#",   "#.#",   "#.#" } ;
//			String[] expected__       = {"#|#", "#|#", "#|#" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}
//		case 1: {
//			String[] map              = { "############",   "#######/....",   "######//####",   "#####//#####",   "####//######",   "..../#######",   "############" };
//			String[] expected__       = {"############", "#######/----", "######//####", "#####//#####", "####//######", "----/#######", "############" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}
//		case 2: {
//			String[] map              = { "#######",   "##/..`#",   "##.##.#",   "##.##.#",   "...../#",   "##.####",   "##.####" };
//			String[] expected__       = {"#######", "##/--`#", "##|##|#", "##|##|#", "--+--/#", "##|####", "##|####" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}
//		case 3: {
//			String[] map              = { "###########.#",   "#/........./.",   "#.#########.#",   "#`........./#",   "#############" };
//			String[] expected__       = {"###########|#", "#/---------/-", "#|#########|#", "#`---------/#", "#############" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}
//		case 4: {
//			String[] map              = { "########.##",   "#./......`#",   "#../.`....#",   "#.`...../.#",   "#....`.../#",   "###.#######" };
//			String[] expected__       = {"########|##", "#./-----+`#", "#.|/-`..||#", "#.`+-+--/|#", "#..|.`---/#", "###|#######" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}
//		case 5: {
//			String[] map              = { "##.########",   "#.........#",   "..`.`.....#",   "#..`......#",   "#.`.`.`...#",   "#....`....#",   "#...`.`.`.#",   "#.........#",   "#.....`./.#",   "#.........#",   "###########" };
//			String[] expected__       = {"##|########", "#.|.......#", "--`-`.....#", "#.|`|.....#", "#.`-`-`...#", "#...|`|...#", "#...`-`-`.#", "#.....|.|.#", "#.....`-/.#", "#.........#", "###########" };
//
//			return verifyCase(casenum, expected__, new MirrorPath().path(map));
//		}

		// custom cases

      case 6: {
			String[] map              = {"##################################################", "#.........../.........`....................../..`#", "#..../........................................../#", "#............................................`..`#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#./.................../............`.............#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#.`../................`........................./#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#................................................#", "#.....................`............/.............#", "#....`............................................", "#................................................#", "#................................................#", "############.#####################################"};
			String[] expected__       = {"##################################################", "#.........../---------`....................../--`#", "#..../------+---------+----------------------+--/#", "#....|......|.........|......................`--`#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#....|......|.........|.........................|#", "#./--+------+---------/------------`............|#", "#.|..|......|.........|............|............|#", "#.|..|......|.........|............|............|#", "#.|..|......|.........|............|............|#", "#.|..|......|.........|............|............|#", "#.`--/------+---------`------------+------------/#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........|............|.............#", "#....|......|.........`------------/.............#", "#....`------+-------------------------------------", "#...........|....................................#", "#...........|....................................#", "############|#####################################"};

			return verifyCase(casenum, expected__, new MirrorPath().path(map));
		}
/*      case 7: {
			String[] map              = ;
			String[] expected__       = ;

			return verifyCase(casenum, expected__, new MirrorPath().path(map));
		}*/
/*      case 8: {
			String[] map              = ;
			String[] expected__       = ;

			return verifyCase(casenum, expected__, new MirrorPath().path(map));
		}*/
		default:
			return -1;
		}
	}
}

// END CUT HERE



不知道什么原因还是有点问题,明天继续写
分享到:
评论

相关推荐

    TC SRM 388 div 2 problem 3

    topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 &lt;= K &lt;= 1000.

    SRM2Mult_1.2_srm2_compositionqw7_

    SRM2Multi dumper for hsap

    VMWARE SRM快速部署手册

    2. **SRM服务器**:运行SRM软件的物理或虚拟服务器,操作系统需为Server 2008 x64。 3. **支持SRM的数据库**:这里指能够被SRM兼容的数据库系统,例如SQL Server 2005。该数据库用于存储SRM的相关配置信息。 4. **...

    SRM SRM 平台功能介绍.pdf

    SAP SRM 介绍

    HASP-SRM-emulator-D.rar_SRM_SRM emulator_emulator_emulator hasp_

    Driver HASP SRM emulator (x86)

    SRM-MDM Catalog Setup – Ready Reference

    根据给定的文件信息,我们将深入探讨“SRM-MDM Catalog Setup – Ready Reference”这一主题,专注于SAP NetWeaver MDM系统中的SRM-MDM目录设置过程。这份文档不仅适用于SAP SRM(Supplier Relationship Management...

    omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册.pdf

    2. OMRON产品命名约定:OMRON公司产品的型号在本手册中都是以大写形式出现,包括“CPM1”,“CPM1A”,“CPM2A”,“CPM2C”,“SRM1(-V2)”等。这可能是为了方便阅读时对产品型号的快速识别。此外,手册中提到的...

    srm image segmentation code

    2. **边界长度**:`srm_boundarylen.cpp`可能是用于计算相邻区域边界的长度,这是评估区域合并代价的另一个因素。较长的边界通常意味着更高的合并成本,因为这会引入更多的不确定性。 3. **SRM主程序**:`srm.m`是...

    SRM.zip_SRM_SRM 分析_steganalysis_隐写分析_集成分类器

    SRM空间富模型隐写分析算法,选区高维特征,使用集成分类器进行训练

    TopCoders:TopCoders 问题

    版本: 1.0.0 作者: Semen Zhydenko ... BridgeCrossingOptimized.java - SRM 146 DIV 2,1000 点问题,时间复杂度 O(n^(n^2))。 BridgeCrossingBest.java - SRM 146 DIV 2,1000 点问题,时间复杂度 O(n)。

    HASP SRM加密狗简介

    HASP SRM加密狗简介 HASP SRM加密狗是一种软件保护解决方案,由阿拉丁公司开发。它提供了多种型号,以满足不同业务需要。下面将对HASP SRM加密狗的各种型号进行详细介绍。 首先是HASP HL基本型,这是阿拉丁公司最...

    SAP-SRM模块快速指南及学习基本知识

    SAP SRM(供应商关系管理)是一种 SAP 产品,有助于通过基于 Web 的平台采购货物。 组织可以采购所有类型的产品,如直接和间接材料,服务,这可以与 SAP ERP 模块和其他非 SAP 后端系统集成,用于会计和计划。 SAP...

    VSAN和SRM.rar

    【标题】"VSAN与SRM"涉及到的是VMware虚拟化环境中的两个关键组件:Virtual SAN(VSAN)和Site Recovery Manager(SRM)。这两个工具在企业级数据中心中发挥着至关重要的作用,确保业务连续性和灾难恢复能力。 VSAN...

    SAP SRM 最新资料

    根据给定的文件信息,我们可以提炼出以下关于SAP SRM(Supplier Relationship Management)的知识点,这主要聚焦于SAP SRM的配置、组件、版权信息以及先修课程建议。 ### SAP SRM概述 SAP SRM是SAP提供的一款用于...

    SRM系统资源管理器

    **SRM系统资源管理器详解** SRM(System Resource Manager)系统资源管理器是一个专为Linux环境设计的工具,它的主要功能是作为一个守护进程在后台持续监控非root用户的进程,以便控制系统的CPU和内存(MEM)资源...

    SAP SRM用途以及功能简介

    2. 扩展、加强与重要供应商的关系:SRM 能够帮助企业与其建立合作关系,共享计划、产品设计和规范信息,并运作方式上进行改进。 3. 建立竞争优势:SRM 能够主动地帮助企业去建立、改进与供应商之间的战略同盟,不是...

    SRM 210 供应商关系管理

    【标题】"SRM 210 供应商关系管理"涉及的是SAP的企业级采购解决方案,SAP Supplier Relationship Management(SRM)系统的一个特定版本。SRM 210是这个模块的一个迭代,旨在帮助企业更有效地管理和优化其与供应商的...

    SRM系统框架

    多年SRM实施经验总结,对希望从事SRM实施或规划的同学们有帮助

    手把手教你玩SRM

    2. **合同管理**:制定明确的合同条款,确保双方权益,同时设定性能指标和违约处理机制。 3. **供应链协同**:通过信息共享,提高供应链的透明度,实现供需同步,减少库存和响应时间。 4. **供应商绩效评估**:...

    SRM系统框架图设计

    分块描述SRM系统的作用:寻源、协同和考核 涉及具体的业务用途,供前期规划作参考,可根据实际情况调整,再考虑如何实现

Global site tag (gtag.js) - Google Analytics