#include<stdio.h> #include<string.h> #include<queue> using namespace std; #define abss(i) -(i) #define check(a) ((a) == 'S' || (a) == '.') #define checkj (j[0] || j[1]) queue <int> que; struct node { int rt, to;//list }lst[6060],arc[50];//POS int head[6060];//no-cross ADT adt NB char s[1505][1505]; int vis[6006],vis1[5]; int n, m, st, cnt; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int j[2]; int vis2[60006]; int check1(int x, int y) { if((x == 1 || x == n) && (y == 1 || y == m)) { int pos = ((x==1?0:1)<<1) | (y==1?0:1); int flag = 0; for(int i = 0; i < 4; i++) if(i != pos && (i^pos) != 3) { int ey = (i&1)?m:1, ex = (i&(2))?n:1; flag |= (s[ex][ey] != '#'); } return flag; } return 0; } int check2(int x, int y) { if(x == n || x == 1 || y == m || y == 1 ) { int ex = x, ey = y; if(ex == 1 || ex == n) ex = ex==1?n:1; else if(ey == 1 || ey == m) ey = ey==1?m:1; return s[ex][ey] != '#'; } return 0; } void build_poi(int x, int y, int rt)//dfs 扫图建点 设置连通块的边(建的点与对应点即为一条边) { int pos ; //add point if(check1(x, y)) { //link pos = (((x==1?0:1)<<1) + (y==1?0:1)); arc[pos].to = head[rt]; head[rt] = abss(pos) - 1;//hash arc[pos].rt = rt; } else if(check2(x, y)) { if(x > 1 && x < n) pos = (x-1) + (y==1?0:(n-2)); else pos = (y-1) + (x==1?0:(m-2)) + n*2-4; lst[pos].to = head[rt]; head[rt] = pos; lst[pos].rt = rt; } if(s[x][y] == 'S') {st = rt;} s[x][y] = 'B'; for(int i = 0; i < 4; i++) { int ex = x + dx[i], ey = y + dy[i]; if(check(s[ex][ey])) build_poi(ex, ey, rt); } } int jmp(int a)// 该函数等价于 v = e[pos].v { if(a <= n-2) return a+n-2; if(a <= 2*n-4) return a-n+2; if(a <= 2*n-4+m-2) return a+m-2; return a-m+2; } void jmp1(int now, int i, int dt)//追踪当前dfs跳了哪些边 { if(now < 0) { now = abss(now+1); if(now - i == -1) j[0] += dt; else if(now - i == 1) j[0] -= dt; else if(now - i == 2) j[1] -= dt; else if(now - i == -2) j[1] += dt; return ; } if(now <= n - 2) j[0] += dt; else if(now <= n*2 - 4) j[0] -= dt; else if(now <= n*2 - 4 + m-2) j[1] += dt; else j[1] -= dt; } int findd(int pos, int rt) { if(!vis2[rt]) {vis2[rt] = 1;que.push(rt);}//设置vis2，及时入队 vis[rt] = 1; if(rt == st) return 1;//同第一行，及时处理 int now = head[rt]; while(now) { if(now > 0) { int tar = jmp(now);//跳边 rt = lst[tar].rt; jmp1(now, 0, 1); if(!vis[rt] && !vis2[rt]) {vis2[rt] = 1;que.push(rt);} if(tar != pos && !vis[rt] && findd(pos, rt)) return 1; if(rt == st && tar != pos && checkj) return 1; jmp1(now ,0, -1); } else { for(int i = 0; i < 4; i++) { if(((abss(now+1))^i) != 3 && arc[i].rt && abss(i)-1 != pos ) { jmp1(now, i, 1); if(!vis2[arc[i].rt] && !vis[arc[i].rt]) {vis2[arc[i].rt] = 1;que.push(arc[i].rt);} if(!vis[arc[i].rt] && findd(pos,arc[i].rt)) return 1; if(arc[i].rt == st && checkj) return 1; jmp1(now, i, -1); } } } now = now>0?lst[now].to:arc[abss(now+1)].to; } return 0; } /* 该题需要测试 s点能访问到的的所有连通块能否访问自身 */ int dfs() { for(int i = 1; i <= cnt; i++) vis2[i] = 0; while(!que.empty()) { int pos = head[que.front()]; st = que.front(); que.pop(); while(pos) { j[0] = j[1] = 0; for(int i = 0; i <= (m+n)<<1; i++) vis[i] = 0; for(int i = 0; i < 5; i++) vis1[i] = 0; vis[st] = 1; if(pos > 0) { jmp1(pos,0,1); if(findd(pos, lst[jmp(pos)].rt)) return 1; jmp1(pos,0,-1); } else { for(int i = 0; i < 4; i++) { if(i != abss(pos+1) && (i^(abss(pos+1)) != 3) && arc[i].rt) { jmp1(pos,i,1); if(findd(pos, arc[i].rt)) return 1; jmp1(pos,i,-1); } } } pos = pos>0?lst[pos].to:arc[abss(pos+1)].to; } } return 0; } int main() { for(int i = 1; i <= 1501; i++) s[0][i] = s[i][0] = '#'; while(~scanf("%d%d",&n,&m)) { for(int i = 1; i <= n; i++) scanf("%s",s[i]+1);if(m + n <= 3) {puts("Yes");continue;} for(int i = 1; i <= n; i++) s[i][m+1] = '#'; for(int i = 1; i <= m; i++) s[n+1][i] = '#'; st = cnt = 0; //build point //存在对点的点 记录至head for(int i = 1; i <= n; i++) {if(check(s[i][1])) build_poi(i, 1, ++cnt);if(check(s[i][m])) build_poi(i, m, ++cnt);} for(int i = 1; i <= m; i++) {if(check(s[1][i])) build_poi(1, i, ++cnt);if(check(s[n][i])) build_poi(n, i, ++cnt);} while(!que.empty()) que.pop(); que.push(st); if(st && dfs()) puts("Yes");// else puts("No"); for(int i = 1; i <= cnt; i++) head[i] = 0; for(int i = 0; i < 5; i++) arc[i].rt = arc[i].to = 0; } return 0; } /* 将二维的图压成一维 此题只有能跳边的点才可能有效，在遍历的时候只需要考虑边界上&&能跳边的点。 不同的连通块之间用边界上的点连接(只有这一种方式) #..## ##S## ##### ..... #.### 只有(1,2)(5,2) 和 (4,1)(4,5)两个点值得记录，因为它们能通向别的区域，并且存在绕回来的可能性。 使用hash映射，将二维的点压成1维。 -0 07 08 09 10 -1 01 04 02 05 03 06 -2 11 12 13 14 -3 左右边上的点满足 (y==1||y==m)&&(1<x<n) 左: x <= n-2 , 右: x <= 2*(n-2) 左右跳边用n-2。 opp = now + n-2 || now - n-2 判断左右关联需要在明确范围后 a == b + n-2 || a == b - (n-2) 上下边同理 跳边用 m-2。 左右边的点二维映射到一维的方式 pos = x-1 + y==1?0:(n-2) 上下 pos = y-1 + x==1?0:(m-2) + 2*(n-2) 四角的点由于和左右上下都可能相连，不能普通处理。 pos = x==1?0:1<<1 + y==1?0:1 分别为 00 01 10 11 首位决定横坐标为1还是n，末位决定纵坐标为1还是m 注，在图中的坐标系为 O y--> x | v 将其整体逆时针旋转90°即可恢复为常见的坐标系。 为了区分，将四角的点映射为负值 -1 -2 -3 -4 pos = abss(now) - 1; 还原用 now = abss(pos+1); 可能跳的边为 for(int i = 0; i < 3; i++) { (i != pos && (i^(abss(pos+1))!=3)); } 满足条件的 i 和 pos 能跳 */
此写法虽然代码量大，运行时间长，但是可以用来演队友。
1 #include<stdio.h> 2 3 char s[1505][1505]; 4 int vx[1505][1505],vy[1505][1505]; 5 int n, m; 6 int dx[4] = {0,0,1,-1}; 7 int dy[4] = {1,-1,0,0}; 8 const int inf = 0X3F3F3F3F; 9 10 int dfs(int sx, int sy) 11 { 12 int x = (sx%n+n)%n, y = (sy%m+m)%m; 13 if(s[x][y] == '#') return 0; 14 if(vx[x][y] != inf) return (sx != vx[x][y] || sy != vy[x][y]); 15 vx[x][y] = sx, vy[x][y] = sy; 16 for(int i = 0; i < 4; i++) 17 if(dfs(sx+dx[i],sy+dy[i])) return 1; 18 return 0; 19 } 20 21 int main() 22 { 23 while(~scanf("%d%d",&n,&m)) 24 { 25 for(int i = 0; i < n; i++) scanf("%s",s[i]); 26 for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) vx[i][j] = vy[i][j] = inf; 27 for(int i = 0; i < n; i++) 28 { 29 for(int j = 0; j < m; j++) 30 { 31 if(s[i][j] == 'S') 32 { 33 if(dfs(i,j)) printf("Yes "); 34 else puts("No"); 35 break; 36 } 37 } 38 } 39 40 } 41 return 0; 42 }
记录第一次到达某点的坐标，以后遍历和第一次对比。
注意要沿着原路径走，否则都是yes。