POJ 3083 Children of the Candy Corn(DFS+BFS)解题报告

2016-07-30 3,635 次浏览 解题报告

题目链接

题目大意

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

解题思路

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

优先级顺序

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

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

#.#
.@.
#.#
路线图(1、2、3 顺序,下同):
#.#
32.
#1#

  1. 前。当不能向左转且前方有路的时候,扶着墙向前走。
    图例:

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

  1. 右。当左方和前方都没有路,且右方有路时,扶墙右转。
    图例:

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

  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 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/07/30/poj-3083.dream

还不快抢沙发

添加新评论