一个每块地板标记着0~9某个数字的迷宫，其中标记1的地板不可以走，标记2~9的地板可以不花时间地跳到任意相同数字的位置，也可以和标记0的地板一样向前后左右任意方向花1个单位时间移动1的距离。给出起点和终点，求起点到终点的最短时间。

 每组数据第一行一个n，表示尺寸，2 <= n <= 100。

接下来n行每行n个0~9的字符，或S表示起点，E表示终点，S和E的运动规则与0相同。整个地图只有一个S和一个E。

 每组数据输出一个数，占一行，表示起点到终点可以花费的最短时间。

如果无法到达重点，输出"Oh No!"

 1 # include <cstdio> 2 # include <queue> 3 # include <cstring> 4 # define N 105 5 using namespace std; 6  7 int n; 8 char g[N][N]; 9 char vis[N][N];10 11 struct pos{int x, y, d;};12 queue <pos> Qst[10];13 pos st;14 15 //描述相邻点的相对位置16 const int dx[] = {0, 0, 1, -1};17 const int dy[] = {1, -1, 0, 0};18 19 int bfs()20 {21     queue <pos> Q;22     Q.push(st);23     //访问标记24     vis[st.x][st.y] = 1;25     while(!Q.empty()){26         pos cur = Q.front();27         Q.pop();28         for(int i = 0; i < 4; ++i){29             pos nst;30             //遍历该店上下左右的点31             nst.x = cur.x + dx[i];32             nst.y = cur.y + dy[i];33             //判断是否还在范围内并且未访问过34             if(1 <= nst.x && nst.x <= n && 1 <= nst.y && nst.y <= n && !vis[nst.x][nst.y]){35                 //访问标记36                 vis[nst.x][nst.y] = 1;37                 char ch = g[nst.x][nst.y];38                 //判断是否找到终点 找到返回步数39                 if(ch == ‘E‘)40                     return cur.d+1;41                 //判断是否遇到阻碍 是的话跳过进入下一次循环42                 if(ch == ‘1‘)43                     continue;44                 //如果是 0 步数加 1 把邻接点压入队列45                 if(ch == ‘0‘)46                     nst.d=cur.d+1, Q.push(nst);47                 //如果是2-9可以“传送”的点 找到与该点数字相同点压入队列48                 else if (‘2‘ <=ch && ch <= ‘9‘){49                     pos nnst;50                     while(!Qst[ch-‘0‘].empty()){51                         nnst = Qst[ch-‘0‘].front();52                         Qst[ch-‘0‘].pop();53                         vis[nnst.x][nnst.y] = 1;54                         nnst.d = cur.d + 1;55                         Q.push(nnst);56                     }57                 }58             }59         }60     }61     return -1;62 }63 64 int main()65 {66     while (~scanf("%d", &n)){67         pos tmp;68         //将队列清空69         for(int i = 2; i <= 9; i++)70             while (!Qst[i].empty())71                 Qst[i].pop();72         for (int i = 1; i <= n; i++){73             scanf("%s", g[i]+1);74             memset(vis[i]+1, 0, sizeof(char)*n);75             for(int j = 1; j <= n; j++){76                 char ch = g[i][j];77                 //把可跳跃位置压入队列78                 if (‘2‘ <= ch && ch <= ‘9‘){79                     tmp.x = i, tmp.y = j;80                     Qst[ch-‘0‘].push(tmp);81                 }82                 //记录初始位置83                 else if (ch == ‘S‘){84                     st.x = i, st.y = j;85                     st.d = 0;86                 }87             }88         }89         int ans = bfs();90         if (ans == -1)91             printf("Oh No!\n");92         else93             printf("%d\n", ans);94     }95     return 0;96 }