题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n×m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 (1,1) 的位置，问能否走到 (n,m) 位置。

输入格式

第一行，两个正整数 n,m。

接下来 nn 行，输入这个迷宫。每行输入一个长为 m 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 (n, m)(n,m)，则输出 Yes；否则输出 No。

输入输出样例

输入 #1

3 5
.##.#
.#...
...#.

输出 #1

Yes

说明/提示

样例解释

路线如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)

数据规模与约定

对于 100% 的数据，保证 1≤n,m≤100，且 (1,1) 和 (n,m) 均为空地。

题解

一道标准的搜索题。

DFS做法:

从(1,1)开始，往上/下/左/右走，每次走一步判断是否越界，在走过的路标上“记号”，以免走进“死胡同”。到了(n,m)则返回true值，结束递归。

注意：本题不用回溯。

话不多说，上代码！

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110];
char ch;
bool flag;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};  //向上/下/左/右走的“标志型”数组
void dfs(int x,int y){
    if(x==n && y==m){
        flag=true;
        return;
    }   //到达终点就返回
    a[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<=0 || xx>n || yy<=0 || yy>m){
            continue;
        }   //判断是否“越界”
        if(a[xx][yy]==0) dfs(xx,yy);    //继续搜索
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch==#) a[i][j]=1;
        }
    }   //读入时，可用“1”表示墙，“0”表示空地
    if(a[1][1]==1 || a[n][m]==1){
        printf("No
");
        return 0;
    }   //特判，如果起点或终点是墙
    dfs(1,1);
    if(flag) printf("Yes
");
    else printf("No
");
   return 0;
}

虽然代码写得烂，但还是杜绝抄袭！！！