[ACM] POJ1024解题报告

98 Replies

思路是board上的.. 经常是不看board没法做啊
思路非常牛B, 来自board上的apunix同学

用BFS,首先设墙和题目已给的路径上的所有点为used，剩余点为unused，然后利用BFS算出从起点到除墙以外的那些点的最短距离，然后利用BFS算出从终点到除墙以外的那些点的最短距离。
（1）判断最短路径是否唯一
如果不唯一，对于那些unused的点，必存在一个点，从起点到这点的最短距离加上从终点到这点的最短距离等于题目给出的最短距离长度
（2）判断墙是否多余
检查题目给出的墙分隔的那些点对，对一个一个被墙分隔的点对(a1,b1),(a2,b2),如果分隔它们的墙是多余的，那么从起点到(a1,b1)的最短距离加上从终点到(a2,b2)的最短距离必大于题目给出的最短距离长度pathlen，且从起点到(a2,b2)的最短距离加上从终点到(a1,b1)的最短距离也必大于pathlen，也就是起点，(a1,b1),(a2,b2),终点不可能在一个最短路径上，也就没必要用墙分隔了

一个小逻辑 有墙多余<=>存在一个墙多余
如果有m个墙是多余的,那么只考虑拿掉这m个墙中的一个其他m-1不动, 这个墙还是多余的, 因为路线完全没有依靠它

我犯了个错误.. 我以为终点一定在[w-1][h-1], 还有有人把每个点到终点/起点的距离初始化为-1, 那么如果有一个区域是封闭的会容易出错.
我是初始化为2E9, 继而中间想到的一个细节是, 这里没问题, 以后如果这些表示正无限的数相加 会超出int表示范围变成负的.. 要小心

代码:

[cpp]#include <iostream>

typedef struct orz {
int d[2]; ///d[0] for distance from start, d[1] for d to end;
bool way;
bool on;
bool s,w; ///if there’s a wall on the south/west of this unit;
} Orz;

Orz a[100][100];
int w,h;

void dij(int o) {
bool end;
end=false;
while(!end) {
end=true;
for(int i=0;i<w;i++)
for(int j=0;j<h;j++) {
if(!a[i][j].on)
continue;
end=false;
if( i-1>=0 && (!a[i][j].w) && a[i][j].d[o]+1<a[i-1][j].d[o]) {
a[i-1][j].d[o]=a[i][j].d[o]+1;
a[i-1][j].on=true;
}
if( j-1>=0 && (!a[i][j].s) && a[i][j].d[o]+1<a[i][j-1].d[o]) {
a[i][j-1].d[o]=a[i][j].d[o]+1;
a[i][j-1].on=true;
}
if( i+1<w && (!a[i+1][j].w) && a[i][j].d[o]+1<a[i+1][j].d[o]) {
a[i+1][j].d[o]=a[i][j].d[o]+1;
a[i+1][j].on=true;
}
if( j+1<h && (!a[i][j+1].s) && a[i][j].d[o]+1<a[i][j+1].d[o]) {
a[i][j+1].d[o]=a[i][j].d[o]+1;
a[i][j+1].on=true;
}
a[i][j].on=false;
}
}
return;
}

int main () {
int t,n,x1,y1,x2,y2,xa,ya,endx,endy;
int wayx,wayy,wayd,wayd_min;
char go;
bool ok;
Orz init;
init.d[0]=init.d[1]=(int)2E9;
init.way=init.on=false;
init.s=init.w=false;

scanf("%d",&t);
while(t–) {
scanf("%d%d",&w,&h);
while(getchar()!=’\n’);

for(int i=0;i<w;i++)
for(int j=0;j<h;j++)
a[i][j]=init;

wayx=wayy=0;
a[0][0].way=true;
wayd=0;
while((go=getchar())!=’\n’) {
wayd++;
switch(go) {
case ‘R’:
wayx++;
break;
case ‘L’:
wayx–;
break;
case ‘U’:
wayy++;
break;
case ‘D’:
wayy–;
}
a[wayx][wayy].way=true;
}
endx=wayx;
endy=wayy;

scanf("%d",&n); //n: num of walls
for(int i=0;i<n;i++) {
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2||y1>y2) {
xa=x1;
ya=y1;
}
else {
xa=x2;
ya=y2;
}
if(x1==x2)
a[xa][ya].s=true;
else
a[xa][ya].w=true;
}

/*
for(int i=0;i<w;i++) {
for(int j=h-1;j>=0;j–) {
if(a[i][j].w)
printf("|");
else
printf(" ");
if(a[i][j].way)
printf("@");
if(a[i][j].s)
printf("___\t");
else
printf(" \t");
}
printf("\n");
} */

a[0][0].on=true;
a[0][0].d[0]=0;
dij(0);

for(int i=0;i<w;i++)
for(int j=0;j<h;j++)
a[i][j].on=false;
a[endx][endy].on=true;
a[endx][endy].d[1]=0;
dij(1);

ok=true;
wayd_min=a[0][0].d[1];
if(wayd_min!=wayd)
ok=false;

if(ok)
for(int i=0;i<w;i++)
for(int j=0;j<h;j++) {
if(a[i][j].way)
continue;
if(a[i][j].d[0]+a[i][j].d[1]<=wayd_min) {
ok=false;
i=w;
break;
}
}

if(ok)
for(int i=1;i<w;i++)
for(int j=0;j<h;j++) {
if(!a[i][j].w)
continue;
if( a[i][j].d[0]+1+a[i-1][j].d[1]>wayd_min
&& a[i][j].d[1]+1+a[i-1][j].d[0]>wayd_min) {
ok=false;
i=w;
break;
}
}

if(ok)
for(int i=0;i<w;i++)
for(int j=1;j<h;j++) {
if(!a[i][j].s)
continue;
if( a[i][j].d[0]+1+a[i][j-1].d[1]>wayd_min
&& a[i][j].d[1]+1+a[i][j-1].d[0]>wayd_min) {
ok=false;
i=w;
break;
}
}

if(ok)
printf("CORRECT\n");
else
printf("INCORRECT\n");
}
return 0;
}[/cpp]

98 thoughts on “[ACM] POJ1024解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *