返回题解分享
讨论 / 题解分享/ 帖子详情

迷宫 - 题解

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=300;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
queue<vector<int>> q;
int main()
{
	cin>>n>>m;
	vector<vector<vector<int>>> f(n,vector<vector<int>>(m,vector<int>(5,0)));
	//存储x,y,当前状态,状态为4时选择0-3四个方向 
	vector<vector<char>> s(n,vector<char>(m));
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	cin>>s[i][j];
	f[1][1][4]=1;//下标从0开始 
	q.push({1,1,4});
	while(q.size())
	{
		vector<int> cur=q.front();
		q.pop();
		int x=cur[0];
		int y=cur[1];
		int d=cur[2];
		
		if(d==4)//选方向 
		{
			for(int i=0;i<4;i++)
			{
				int nx=x+dx[i],ny=y+dy[i];
				int nd=i;
				if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]=='.')
				{
					if(f[nx][ny][nd]==0)
					{
						f[nx][ny][nd]=1;
						q.push({nx,ny,nd});
					}	
				}
			}
		}
		else//固定路线一直走 
		{
			int nx=x+dx[d];
			int ny=y+dy[d];
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]=='.')
			{
				if(f[nx][ny][d]==0)
				{
					f[nx][ny][d]=1;
					q.push({nx,ny,d});
				}	
			}
			else//到边界 
			{
				if(f[x][y][4]==0)
				{
					f[x][y][4]=1;
					q.push({x,y,4});
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			for(int d=0;d<5;d++)
			{
				if(f[i][j][d]==1)
				{
					ans++;
					break;//防重复,当前坐标下有一个方向标记即可 
				}
			}
		}
	}
	cout<<ans;
	return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!