题目链接

题目大意

给定一个二维迷宫， "#" 表示不可走的位置，“.” 表示可走的位置，起点为 “S”，终点为 “E”。问左手扶墙走、右手扶墙走和最短路线的步数各是多少。

解题思路

本题需要输入三种走迷宫的方式所需的步数，最后一种显然是裸的 BFS。那么本题的难点主要集中在前两种：左手扶墙走和右手扶墙走。

优先级顺序

首先说结论，左手扶墙的优先级顺序为：左、前、右、后。右手扶墙的优先级顺序为：右、前、左、后。下面只简单分析一下左手时的情况，右手同理。

左。如果我们扶着墙一路走来，遇到一个可以向左转的岔路口，由生活经验可知，我们一定会扶着墙左转。
图例：人当前位置在 “@” 处，朝向为图中向上的方向，下同。

#.#
.@.
#.#
路线图（1、2、3 顺序，下同）：
#.#
32.
#1#

前。当不能向左转且前方有路的时候，扶着墙向前走。
图例：

#.#
#@.
#.#
路线图：
#3#
#2.
#1#

右。当左方和前方都没有路，且右方有路时，扶墙右转。
图例：

###
#@.
#.#
路线图：
###
#23
#1#

后。当左、前、右都没有路的时候，只能掉头原路返回。
图例：

###
#@#
#.#
路线图：
### → ###
#2# → #2#
#1# → #3#

误区

应特别注意的是，方向优先级顺序的方向是相对于人的朝向来说的，这也是我们用 “前”、“后” 而不是 “上”、“下” 来描述方向的原因。以左手扶墙为例，如果当前人的朝向在地图上看来是向上的，那么此时的方向优先级顺序为：左、上、右、下；而如果人的朝向向左，那么方向优先级顺序则应变为：下、左、上、右。其他情况同理。

实现细节

对于方向，我们可以设置一个二维数组来表示不同方向的位移偏移量，左手扶墙时顺序遍历该数组，右手扶墙时逆序遍历。在 DFS 时，无需设置标记数组，由于是扶墙走，只要扶墙方式、朝向和地图确定，那么下一步走的位置也就是确定的，所以确定下一步的位置后就只需递归一次并在回溯后直接 return。

参考代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct info {
    int x, y;
    int step;
} s;
int w, h, sx, sy;
char graph[40][41];
bool vis[40][40];
int dir[4][2] = {
        {0, -1}, {-1, 0},
        {0, 1}, {1, 0},
    };
int lcnt, rcnt;

bool Judge(int x, int y) {
    if(x>=0 && x<h && y>=0 && y<w
        && graph[x][y]!='#')
        return true;
    else return false;
}

void LDFS(int x, int y, int d) {    //d为当前朝向
    lcnt++;
    if(graph[x][y] == 'E') return;
    d = (d-1+4) % 4;    //按照优先级顺序。最开始的方向是左，即当前朝向-1
    for(int i=d; i<=3; ++i) {
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if(Judge(next_x, next_y)) {
            LDFS(next_x, next_y, i);
            return;    //找到可走位置，DFS结束后直接return
        }
    }
    for(int i=0; i<d; ++i) {
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if(Judge(next_x, next_y)) {
            LDFS(next_x, next_y, i);
            return;
        }
    }
}

void RDFS(int x, int y, int d) {
    rcnt++;
    if(graph[x][y] == 'E') return;
    d = (d+1) % 4;    //按照优先级顺序。最开始的方向是右，即当前朝向+1
    for(int i=d; i>=0; --i) {
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if(Judge(next_x, next_y)) {
            RDFS(next_x, next_y, i);
            return;    //找到可走位置，DFS结束后直接return
        }
    }
    for(int i=3; i>d; --i) {
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if(Judge(next_x, next_y)) {
            RDFS(next_x, next_y, i);
            return;
        }
    }
}

int BFS() {
    memset(vis, false, sizeof(vis));
    info s = {sx, sy, 1};
    queue<info> q;
    q.push(s);
    vis[sx][sy] = true;
    while(!q.empty()) {
        info f = q.front();
        q.pop();
        for(int i=0; i<4; ++i) {
            info next = f;
            if(graph[f.x][f.y] == 'E')
                return f.step;
            next.x += dir[i][0];
            next.y += dir[i][1];
            if(Judge(next.x, next.y) && !vis[next.x][next.y]) {
                next.step++;
                q.push(next);
                vis[next.x][next.y] = true;
            }
        }
    }

    return -1;
}

int main(int argc, char const *argv[]) {
    int n;
    scanf("%d", &n);
    while(n--) {
        scanf("%d %d", &w, &h);
        bool found = false;
        for(int i=0; i<h; ++i) {
            scanf("%s", graph[i]);
            for(int j=0; j<w && !found; ++j) {
                if(graph[i][j] == 'S') {
                    found = true;
                    sx = i;
                    sy = j;
                    break;
                }
            }
        }
        lcnt = rcnt = 0;
        LDFS(sx, sy, 0);
        RDFS(sx, sy, 0);
        int min_step = BFS();
        printf("%d %d %d\n", lcnt, rcnt, min_step);
    }
    
    return 0;
}

bLue's blog