[ACM] POJ1024解题报告

思路是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表示范围变成负的.. 要小心

代码:

1#include <iostream>
2 
3typedef struct orz {
4    int d[2];  ///d[0] for distance from start, d[1] for d to end;
5    bool way;
6    bool on;
7    bool s,w;   ///if there's a wall on the south/west of this unit;
8} Orz;
9 
10Orz a[100][100];
11int w,h;
12 
13void dij(int o) {
14    bool end;
15    end=false;
16    while(!end) {
17        end=true;
18        for(int i=0;i<w;i++)
19            for(int j=0;j<h;j++) {
20                if(!a[i][j].on)
21                    continue;
22                end=false;
23                if( i-1>=0 && (!a[i][j].w) && a[i][j].d[o]+1<a[i-1][j].d[o]) {
24                    a[i-1][j].d[o]=a[i][j].d[o]+1;
25                    a[i-1][j].on=true;
26                }
27                if( j-1>=0 && (!a[i][j].s) && a[i][j].d[o]+1<a[i][j-1].d[o]) {
28                    a[i][j-1].d[o]=a[i][j].d[o]+1;
29                    a[i][j-1].on=true;
30                }
31                if( i+1<w && (!a[i+1][j].w) && a[i][j].d[o]+1<a[i+1][j].d[o]) {
32                    a[i+1][j].d[o]=a[i][j].d[o]+1;
33                    a[i+1][j].on=true;
34                }
35                if( j+1<h && (!a[i][j+1].s) && a[i][j].d[o]+1<a[i][j+1].d[o]) {
36                    a[i][j+1].d[o]=a[i][j].d[o]+1;
37                    a[i][j+1].on=true;
38                }
39                a[i][j].on=false;
40            }
41    }
42    return;
43}
44 
45int main () {
46    int t,n,x1,y1,x2,y2,xa,ya,endx,endy;
47    int wayx,wayy,wayd,wayd_min;
48    char go;
49    bool ok;
50    Orz init;
51    init.d[0]=init.d[1]=(int)2E9;
52    init.way=init.on=false;
53    init.s=init.w=false;
54 
55    scanf("%d",&t);
56    while(t--) {
57        scanf("%d%d",&w,&h);
58        while(getchar()!='\n');
59 
60        for(int i=0;i<w;i++)
61            for(int j=0;j<h;j++)
62                a[i][j]=init;
63 
64        wayx=wayy=0;
65        a[0][0].way=true;
66        wayd=0;
67        while((go=getchar())!='\n') {
68            wayd++;
69            switch(go) {
70                case 'R':
71                    wayx++;
72                    break;
73                case 'L':
74                    wayx--;
75                    break;
76                case 'U':
77                    wayy++;
78                    break;
79                case 'D':
80                    wayy--;
81            }
82            a[wayx][wayy].way=true;
83        }
84        endx=wayx;
85        endy=wayy;
86 
87        scanf("%d",&n); //n: num of walls
88        for(int i=0;i<n;i++) {
89            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
90            if(x1>x2||y1>y2) {
91                xa=x1;
92                ya=y1;
93            }
94            else {
95                xa=x2;
96                ya=y2;
97            }
98            if(x1==x2)
99                a[xa][ya].s=true;
100            else
101                a[xa][ya].w=true;
102        }
103 
104/*
105        for(int i=0;i<w;i++) {
106            for(int j=h-1;j>=0;j--) {
107                if(a[i][j].w)
108                    printf("|");
109                else
110                    printf(" ");
111                if(a[i][j].way)
112                    printf("@");
113                if(a[i][j].s)
114                    printf("___\t");
115                else
116                    printf(" \t");
117            }
118            printf("\n");
119        }                   */
120 
121        a[0][0].on=true;
122        a[0][0].d[0]=0;
123        dij(0);
124 
125        for(int i=0;i<w;i++)
126            for(int j=0;j<h;j++)
127                a[i][j].on=false;
128        a[endx][endy].on=true;
129        a[endx][endy].d[1]=0;
130        dij(1);
131 
132        ok=true;
133        wayd_min=a[0][0].d[1];
134        if(wayd_min!=wayd)
135            ok=false;
136 
137        if(ok)
138            for(int i=0;i<w;i++)
139                for(int j=0;j<h;j++) {
140                    if(a[i][j].way)
141                        continue;
142                    if(a[i][j].d[0]+a[i][j].d[1]<=wayd_min) {
143                        ok=false;
144                        i=w;
145                        break;
146                    }
147                }
148 
149        if(ok)
150            for(int i=1;i<w;i++)
151                for(int j=0;j<h;j++) {
152                    if(!a[i][j].w)
153                        continue;
154                    if( a[i][j].d[0]+1+a[i-1][j].d[1]>wayd_min
155                    &&  a[i][j].d[1]+1+a[i-1][j].d[0]>wayd_min) {
156                        ok=false;
157                        i=w;
158                        break;
159                    }
160                }
161 
162        if(ok)
163            for(int i=0;i<w;i++)
164                for(int j=1;j<h;j++) {
165                    if(!a[i][j].s)
166                        continue;
167                    if( a[i][j].d[0]+1+a[i][j-1].d[1]>wayd_min
168                    &&  a[i][j].d[1]+1+a[i][j-1].d[0]>wayd_min) {
169                        ok=false;
170                        i=w;
171                        break;
172                    }
173                }
174 
175        if(ok)
176            printf("CORRECT\n");
177        else
178            printf("INCORRECT\n");
179    }
180    return 0;
181}

Leave a Reply

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