bmqnc
- 浏览: 127505 次
- 性别:
- 来自: 上海
-
文章分类
最新评论
-
lliiqiang：
最简单的显示 存储分离，有的时候错别字与错误数据存储兼容。还有 ...
关于软件可扩展性与代码防御性编程的一点思考 -
bmqnc：
cqh520llr 写道sb，不帖代码，以后人家搜索到了浪费人 ...
今天自己做了redo-undo功能 -
cqh520llr：
我也觉得，代码风格和不定性样式太多了，
编码风格不取决于自己，取决于领导班子和现有代码 -
cqh520llr：
sb，不帖代码，以后人家搜索到了浪费人家时间，而且这个代码贴出 ...
今天自己做了redo-undo功能 -
shiqicai：
太隐晦，看不懂。
康神与顿神
这题的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
不知道什么原因还是有点问题，明天继续写
分享到：
发表评论
-
SRM 499 DIV2
2011-03-09 17:00 709250的和500的偏简单，就不说了，500的想明白了很简单，代 ... -
最近写Trie tree速度有点慢了
2010-11-02 16:42 803很长时间没写数据结构了，我发现我写Trie tree的速度都有 ... -
关于API设计的tricky的地方与pitfalls
2010-10-12 17:28 762今天看项目中的一段代码，看完之后我对原来的程序员真是抓狂了，代 ... -
SRM 253 div2 1000pts
2010-09-21 14:30 977这题不难，用bfs，bfs的时候注意剪一个枝就行了。代码如下： ... -
srm 235 div2 1000pts
2010-09-21 10:08 745这个srm的500pts要讲一下，这题主要关键点在于要将tar ... -
Srm 231 div2 900pts
2010-09-17 15:57 928这题很简单，用贪心的。最基本的想法就是任务建立的时间是不能省的 ... -
srm 227 div2 1000pts
2010-09-16 13:20 718这题如果用暴力的方法的话，其实是求排列组合的值。 但是要注意的 ... -
Srm 225 div2 1000pts
2010-09-15 13:59 970这题很简单，只要会灵活的运用java的库函数即可，当然，库函数 ... -
SRM 233 DIv2 1000pts
2010-09-14 14:33 771这题蛮简单的，就是求符合条件的最大子集，很简单。 代码如下： ... -
srm 234 div2 1000pts
2010-09-03 13:08 823这题仔细分析一下还是蛮简单的，利用正则表达式来做。正则表达式分 ... -
SRM div2 312 1000pts
2010-08-23 15:04 815一开始想错了，走了很多弯路，看来一开始就要想清楚才对。 -
SRM 479 Div2
2010-08-19 16:49 824第一题，简单，不做任何说明,直接上代码： public c ... -
SRM 452 Div2 1000pts
2010-05-27 22:16 1024这题不难，求哈密顿路的，就是多了一个限制条件。 主要是合并满 ... -
SRM313 DIV2 1000pts
2010-04-30 12:02 784最近做了很多题，但是又太懒，总不想写解题报告。从现在开始，每次 ... -
算法题中超级小不心的地方
2010-04-04 18:52 794一个是数据计算上的精度问题，即中间过程计算的结果可能超出数据所 ... -
POJ错误！极品诡异，我在以下网址提交系统判断正确，poj上却判断错误
2010-03-15 15:24 843如题，我在：http://acm.xtu.edu.cn/Onl ...
相关推荐
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k，给定N和K，计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
SRM2Multi dumper for hsap
2. **SRM服务器**：运行SRM软件的物理或虚拟服务器，操作系统需为Server 2008 x64。 3. **支持SRM的数据库**：这里指能够被SRM兼容的数据库系统，例如SQL Server 2005。该数据库用于存储SRM的相关配置信息。 4. **...
SAP SRM 介绍
Driver HASP SRM emulator (x86)
根据给定的文件信息，我们将深入探讨“SRM-MDM Catalog Setup – Ready Reference”这一主题，专注于SAP NetWeaver MDM系统中的SRM-MDM目录设置过程。这份文档不仅适用于SAP SRM（Supplier Relationship Management...
2. OMRON产品命名约定：OMRON公司产品的型号在本手册中都是以大写形式出现，包括“CPM1”，“CPM1A”，“CPM2A”，“CPM2C”，“SRM1(-V2)”等。这可能是为了方便阅读时对产品型号的快速识别。此外，手册中提到的...
2. **边界长度**：`srm_boundarylen.cpp`可能是用于计算相邻区域边界的长度，这是评估区域合并代价的另一个因素。较长的边界通常意味着更高的合并成本，因为这会引入更多的不确定性。 3. **SRM主程序**：`srm.m`是...
SRM空间富模型隐写分析算法,选区高维特征，使用集成分类器进行训练
版本： 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 HL基本型，这是阿拉丁公司最...
SAP SRM（供应商关系管理）是一种 SAP 产品，有助于通过基于 Web 的平台采购货物。 组织可以采购所有类型的产品，如直接和间接材料，服务，这可以与 SAP ERP 模块和其他非 SAP 后端系统集成，用于会计和计划。 SAP...
【标题】"VSAN与SRM"涉及到的是VMware虚拟化环境中的两个关键组件：Virtual SAN（VSAN）和Site Recovery Manager（SRM）。这两个工具在企业级数据中心中发挥着至关重要的作用，确保业务连续性和灾难恢复能力。 VSAN...
根据给定的文件信息，我们可以提炼出以下关于SAP SRM（Supplier Relationship Management）的知识点，这主要聚焦于SAP SRM的配置、组件、版权信息以及先修课程建议。 ### SAP SRM概述 SAP SRM是SAP提供的一款用于...
**SRM系统资源管理器详解** SRM（System Resource Manager）系统资源管理器是一个专为Linux环境设计的工具，它的主要功能是作为一个守护进程在后台持续监控非root用户的进程，以便控制系统的CPU和内存（MEM）资源...
2. 扩展、加强与重要供应商的关系：SRM 能够帮助企业与其建立合作关系，共享计划、产品设计和规范信息，并运作方式上进行改进。 3. 建立竞争优势：SRM 能够主动地帮助企业去建立、改进与供应商之间的战略同盟，不是...
【标题】"SRM 210 供应商关系管理"涉及的是SAP的企业级采购解决方案，SAP Supplier Relationship Management（SRM）系统的一个特定版本。SRM 210是这个模块的一个迭代，旨在帮助企业更有效地管理和优化其与供应商的...
多年SRM实施经验总结，对希望从事SRM实施或规划的同学们有帮助
2. **合同管理**：制定明确的合同条款，确保双方权益，同时设定性能指标和违约处理机制。 3. **供应链协同**：通过信息共享，提高供应链的透明度，实现供需同步，减少库存和响应时间。 4. **供应商绩效评估**：...
分块描述SRM系统的作用：寻源、协同和考核 涉及具体的业务用途，供前期规划作参考，可根据实际情况调整，再考虑如何实现