。

题意：

先沿着左边的墙从 S 一直走，求到达 E 的步数。

再沿着右边的墙从 S 一直走，求到达 E 的步数。

最后求最短路。

 

分析：

最短路好办，关键是沿着墙走不太好想。

但只要弄懂如何转，这题就容易了。

单就沿着左走看一下：

当前方向 　　  检索顺序

     ↑ ：    　　← ↑ → ↓

    → ：    　   ↑ → ↓ ← 

     ↓ ：    　　→ ↓ ← ↑ 

    ← ：    　   ↓ ← ↑ → 

如此，规律很明显，假设数组存放方向为 ← ↑ → ↓， 如果当前方向为 ↑， 就从 ← 开始依次遍历，找到可以走的，如果 ← 可以走，就不用再看 ↑ 了。

在DFS时，加一个参数，用来保存当前的方向。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 100+10;int dx[] = {
   0, -1, 0, 1};int dy[] = {-1, 0, 1, 0};int dl[][2] = {
   {
   0, -1}, {-1, 0}, {
   0, 1}, {
   1, 0}};int dr[][2] = {
   {
   0, 1}, {-1, 0}, {
   0, -1}, {
   1, 0}};int sx, sy, ex, ey, n, m;char G[maxn][maxn];struct Pos {    int x, y, s;};int dfs(int x, int y, int d, int step, int dir[][2]) {    for(int i=0; i<4; i++) {        int j = ((d-1+4)%4+i)%4;        int nx = x+dir[j][0];        int ny = y+dir[j][1];        if(nx == ex && ny == ey) return step+1;        if(nx < 0 || ny < 0 || nx > n || ny > m) continue;        if(G[nx][ny] == '#') continue;        return dfs(nx, ny, j, step+1, dir);    }}int BFS(int sx, int sy) {    bool vis[maxn][maxn];    memset(vis, false, sizeof(vis));    queue
          
            Q; Q.push((Pos){sx, sy, 1}); vis[sx][sy] = true; while(!Q.empty()) { Pos p = Q.front(); Q.pop(); if(p.x == ex && p.y == ey) return p.s; Pos np; for(int d=0; d<4; d++) { np.x = p.x + dx[d]; np.y = p.y + dy[d]; np.s = p.s + 1; if(np.x < 0 || np.x > n || np.y < 0 || np.y > m) continue; if(vis[np.x][np.y]) continue; if(G[np.x][np.y] != '#') { vis[np.x][np.y] = true; Q.push(np); } } } return -1;}int main() { int T, d1, d2; //freopen("my.txt", "r", stdin); scanf("%d", &T); while(T--) { scanf("%d%d", &m, &n); for(int i=0; i