搜索之走迷宫

来源：C++信息学一本通

题目

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

输入

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用’.‘表示，有障碍物的格子用’#‘表示。
迷宫左上角和右下角都是’.’。

输出

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

样例输入

5 5

. . # # #

# . . . .

# . # . #

# . # . #

# . # . .

样例输出

9

这道题还是搜索

还是要写函数

今天就不心情复杂了

我就是这么幽默

咳咳咳

回归正题

先看一下样例

这个很简单

在它遍历的时候

悄悄地

悄悄地

给它累加

圣旨到

int dfs(int x,int y) { if(x==fx&&y==fy)//判断是否到达终点  { return ans; } else { for(int i=0;i<4;i++)//上下左右四个方向  { int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=0 && nx<=n && ny>=0 && ny<=m && tmp[nx][ny]==0 && b[nx][ny]==0 && (a[nx][ny]=='.' || a[nx][ny]=='T') )//判断是否出界 & 是否访问过 & 不是陷阱  { if(f==0) ans++; //累加                  tmp[nx][ny]=1; if(nx==fx && ny==fy) {      f=1; } dfs(x+dx[i],y+dy[i]); } } } } 

当然

我知道你又有那个疑问

if判断条件 & if里边是啥子嘞

咱先给他拎出来

if(nx>=0 && nx<=n && ny>=0 && ny<=m && tmp[nx][ny]==0 && b[nx][ny]==0 && (a[nx][ny]=='.' || a[nx][ny]=='T') )//判断是否出界 & 是否访问过 & 不是陷阱  { if(f==0) ans++; //累加                  tmp[nx][ny]=1; if(nx==fx && ny==fy) {      f=1; } dfs(x+dx[i],y+dy[i]); } 

原本呢

是不用加后面那一个判断条件

但是

咳咳咳

接着说

因为第一次试的时候 发现这个程序时错误的

调了半天才发现

如果直接判断a[nx][ny]!=陷阱

就是错的

再说if里边的那个

 if(f==0) ans++; //累加               tmp[nx][ny]=1; if(nx==fx && ny==fy) {      f=1; } 

第二个if应该能看懂

判断是否到达终点

并且打标记

再说第一个if

我的这个到了终点之后

竟然不回家[主函数]

所以就打了个标记 并且判断

要不然它会继续累加

皇上驾到

#include<iostream> using namespace std; char a[10][10]; int b[10][10]; bool tmp[10][10],f=0; int dx[4]={0,0,1,-1}; int dy[4]={-1,1,0,0}; int ans,fx,fy,sx,sy,T,n,m,l,r; int dfs(int x,int y) { if(x==fx&&y==fy)//判断是否到达终点  { return ans; } else { for(int i=0;i<4;i++)//上下左右四个方向  { int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=0 && nx<=n && ny>=0 && ny<=m && tmp[nx][ny]==0 && b[nx][ny]==0 && (a[nx][ny]=='.' || a[nx][ny]=='T') )//判断是否出界 & 是否访问过 & 不是陷阱  { if(f==0) ans++; //累加                  tmp[nx][ny]=1; if(nx==fx && ny==fy) {      f=1; } dfs(x+dx[i],y+dy[i]); } } } } int main() {     cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) {    cin>>a[i][j]; if(a[i][j]=='#') b[i][j]=1; } }   sx=1;sy=1;fx=n;fy=m;  tmp[sx][sy]=1; dfs(sx,sy);     cout<<ans<<endl; return 0; } 

复制的记得

爱赞不赞

爱吐槽就吐吧

有问题可以在下边提出来记得

@Y_bluefat