題意：求起始點到任意一條邊的最短距離。規則是：可以拐彎的話就不能直走，否則直走
思路：BFS，不過vis的標記數組要變成三維的，記錄從四個方向進來的可能
#include#include #include #include #include using namespace std; const int MAXN = 110; struct node{ int x,y,p; int s; }q[MAXN*MAXN*4],tmp; int map[MAXN][MAXN],n,m; int vis[MAXN][MAXN][4]; int sx,sy; char str[MAXN]; int dir[4][2] = {1,0,0,1,-1,0,0,-1}; int bfs(){ if (sx == 1 || sx == n || sy == 1 || sy == m) return 0; int head,tail,x,y,s,p; memset(vis,0,sizeof(vis)); for (int i = 0; i < 4; i++) vis[sx][sy][i] = 1; head = tail = 0; tmp.x = sx,tmp.y = sy,tmp.s = 0,tmp.p = -1; q[head] = tmp; while (head <= tail){ int flag = 0; x = q[head].x,y = q[head].y; s = q[head].s,p = q[head].p; for (int i = 0; i < 4; i++) if (p < 0 || (p&1) != (i&1)){ tmp.x = x + dir[i][0]; tmp.y = y + dir[i][1]; if (map[tmp.x][tmp.y] == 0) continue; flag = 1; if (vis[tmp.x][tmp.y][i]) continue; tmp.s = s + 1,tmp.p = i; if (tmp.x == 1 || tmp.x == n || tmp.y == 1 || tmp.y == m) return tmp.s; vis[tmp.x][tmp.y][i] = 1; q[++tail] = tmp; } if (!flag){ tmp.x = x + dir[p][0]; tmp.y = y + dir[p][1]; if (map[tmp.x][tmp.y] != 0 && vis[tmp.x][tmp.y][p] == 0){ tmp.s = s + 1,tmp.p = p; if (tmp.x == 1 || tmp.x == n || tmp.y == 1 || tmp.y == m) return tmp.s; vis[tmp.x][tmp.y][p] = 1; q[++tail] = tmp; } } ++head; } return -1; } int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d%d",&n,&m); memset(map,0,sizeof(map)); for (int i = 1; i <= n; i++){ scanf("%s",str); for (int j = 0; j < m; j++) if (str[j] == '#') map[i][j+1] = 0; else { map[i][j+1] = 1; if (str[j] == '@') sx = i,sy = j+1; } } printf("%d\n",bfs()); } return 0; }
