C++走迷宫问题

迷宫基本构成：起点，终点，障碍

1.方向数组

方向数组是解决迷宫问题必不可少的“利器”，它能使遍历某个位置的前、后、左、右更加方便。

例如：

#include <bits/stdc++.h>
using namespace std;
int fx[5]={0,0,1,-1};
int fy[5]={1,-1,0,0};
//fx数组控制上下，fy数组控制左右 
int a[110][110],n,m;
int main() 
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];//输入 
		}
	}
	int x,y; 
	cin>>x>>y;
	for(int i=0;i<4;i++)//遍历方向 
	{
		int nx=x,ny=y;
		nx+=fx[i];
		ny+=fy[i];
		if(nx<1||ny<1||nx>n||ny>m)continue;//溢出 
		cout<<a[nx][ny]<<endl;
	} 
	return 0;
}

2.迷宫路径dfs

求路径数通常用dfs搜索

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int cnt=0,n,m;
char s[10][10];
bool vis[10][10];//查看是否已经走过
void dfs(int x,int y)
{
	if(x==n&&y==m)//到达终点
	{
		cnt++;
		return;
	}
	vis[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]=='#'||vis[nx][ny])continue;//判断不符合
		dfs(nx,ny);//回溯
	}
	vis[x][y]=0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)cin>>s[i][j];
	}
	dfs(1,1);
	if(cnt)cout<<cnt;
	else cout<<-1;//走不了
	return 0; 
}

3. 迷宫路径bfs

求路径数也可以用bfs搜索

#include<bits/stdc++.h>//本代码解决了收集星星问题 
using namespace std;
const int N=250;
char s[N][N];
int n,m,stx,sty,cnt;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
bool vis[N][N];
struct node
{
	int x,y;	
};
void bfs()
{
	queue<node>q;
	q.push({stx,sty});
	vis[stx][sty]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		if(s[now.x][now.y]=='*')cnt++;
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]=='#'||vis[nx][ny])continue;
			q.push({nx,ny});
			vis[nx][ny]=1;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
			if(s[i][j]=='S')
			{
				stx=i;
				sty=j;
			}
		}
	}
	bfs();//bfs没有参数 
	cout<<cnt;
	return 0; 
}

4.连通块问题

#include<bits/stdc++.h>
using namespace std;
const int N=105;
bool s[N][N];
int n,m,stx,sty,cnt,xmax;
int dx[5]={0,0,1,-1};//方向数组 
int dy[5]={1,-1,0,0};
bool vis[N][N]; 
void dfs(int x,int y)
{
	vis[x][y]=1;
	cnt++;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]==0||vis[nx][ny])continue;//判断跳过 
		dfs(nx,ny);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]==1&&vis[i][j]==0)
			{
				cnt=0;
				dfs(i,j);
				xmax=max(cnt,xmax);//比大小 
			}
		}
	}
	cout<<xmax;
	return 0; 
}

5.最短路

最短路只能用bfs解决

#include<bits/stdc++.h>
using namespace std;
const int N=50;
char s[N][N];
int n,m,stx=1,sty=1,cnt,dis[N][N];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
bool vis[N][N];
struct node
{
	int x,y;	
};
void bfs()
{
	queue<node>q;
	q.push({stx,sty});
	vis[stx][sty]=1;
	dis[stx][sty]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]=='#'||vis[nx][ny])continue;
			q.push({nx,ny});
			dis[nx][ny]=dis[now.x][now.y]+1;
			vis[nx][ny]=1;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
			}	
	} 
	bfs();
	cout<<dis[n][m];
	return 0; 
}