4 条题解

  • 0
    @ 2025-3-25 22:49:08
    #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;
    }
    

    信息

    ID
    297
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    43
    已通过
    17
    上传者