搜索之走迷宫|题解

搜索之走迷宫

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

题目

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

输入

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

输出

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

样例输入

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

上一篇:UPC-穿越


下一篇:NOIP 2010 P1514 引水入城