迷宫问题答案

题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】

第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

【输出】

k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

【输入样例】

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

【输出样例】

YES
NO

程序

#include <iostream>
using namespace std;
int ha,la,hb,lb;
int n;
int vis[110][110];
int u[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
// 0 1
// 0 -1
int flag;
void search(int x,int y){
    if(x==hb && y==lb){
        flag=1;
        cout<<"YES";
        return;
    }
    for(int i=0;i<=3;i++){
        int xx=x+u[i][0];
        int yy=y+u[i][1];
        if(xx>=0&&xx<n && yy>=0 && yy<n && vis[xx][yy]!=1){
            vis[xx][yy]=1; //标记为1,表示这个点用过了
            search(xx,yy);
        }
    }
}
int main()
{
    int time;
    char t;
    cin>>time;
    int i;
    for(i=1;i<=time;i++){
        flag=0;
        cin>>n;
        memset(vis,0,sizeof(vis));// 重新初始化为0
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                cin>>t;
                if(t=='#')
                    vis[x][y]=1;
            }
        }
        cin>>ha>>la>>hb>>lb;
        search(ha,la);
        if(flag==0) cout<<"NO";
    }
    return 0;
}

简析

标准的二维数组移动类问题，可参考

• 深度优先搜索系列一 leetcode题库 200 岛屿数量
• 深度优先搜索系列四-岛屿面积
• 搜索和回溯系列十七 找出不同字母的个数

判断条件也比较简单，从这个点出发，搜索所有能走到的点，如果当前搜索的点到达了目标点，flag标记为true，返回即可。若所有能到达的点都搜索完了，flag仍为false，则无法到达。