求助!!!迷宫最短路径(DFS)
  • 板块学术版
  • 楼主Yee_Aries
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/7/21 23:27
  • 上次更新2023/11/4 13:53:37
查看原帖
求助!!!迷宫最短路径(DFS)
151481
Yee_Aries楼主2021/7/21 23:27
#include<bits/stdc++.h>
using namespace std;
int n,m,s1,s2,g1,g2,sum[101][101];
int dx[4]={1,-1,0,0},
	dy[4]={0,0,1,-1};
char a[101][101];
void dfs(int x,int y)
{
	if(a[x][y]=='G')
	  exit(0);
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			int tx=x+dx[i],ty=y+dy[j];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&sum[tx][ty]==0&&a[tx][ty]!='#')
			{
				sum[tx][ty]=sum[x][y]+1;
				dfs(tx,ty);
				sum[tx][ty]=0; 
			}
		}
	}
	exit(0);
}
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]=='S')
	    	{
	    		s1=i;
	    		s2=j;
			}
			if(a[i][j]=='G')
			{
				g1=i;
				g2=j;
			}
		}
	}
	dfs(s1,s2);
	if(!sum[g1][g2])
	  cout<<sum[g1][g2]<<endl;
	else
	  cout<<"INF"<<endl;
	return 0;
}
//输入样例1
//5 5   
//#S###
//...#.
//.#...
//###.#
//..G.#
//输出样例1
//7
//输入样例2
//2 2                   
//#S
//G#
//输出样例2
//INF

无输出

2021/7/21 23:27
加载中...