0分求助
查看原帖
0分求助
427045
cwxcplh楼主2023/7/1 14:25

用bfs打了一下这题,结果全WA,有哪位大神能帮忙看一下吗?

#include<bits/stdc++.h>
using namespace std;
struct oibh{
	int x,y,s;
}st,nx;
queue <oibh> q;
int n,m,ss,ans,b[506][506],fx[4][2]={1,0,0,-1,-1,0,0,1};
char mp[506][506];
int bfs()
{
	int i;
	while(!q.empty())
	{
		for(i=0;i<4;i++)
		{
			nx.x=q.front().x+fx[i][0];
			nx.y=q.front().y+fx[i][1];
			nx.s=q.front().s+1;
			ss=q.front().s;
			if(mp[nx.x][nx.y]=='0'&&((nx.x==0||nx.x==n-1)||(nx.y==0||nx.y==m-1)))
			{
				return 0;
			}
			if(mp[nx.x][nx.y]=='*')
			{
				nx.x=nx.y=nx.s=0;
				continue;
			}
			if(nx.x>0&&nx.x<n-1&&nx.y>0&&nx.y<m-1&&b[nx.x][nx.y]==0&&mp[nx.x][nx.y]=='0')
			{
				b[nx.x][nx.y]=1;
				q.push(nx);
			}
		}
		q.pop();
	}
	return ss;
}
int main()
{
	int i,j;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			cin>>mp[i][j];
		}
	}
	for(i=1;i<n-1;i++)
	{
		for(j=1;j<m-1;j++)
		{
			if(mp[i][j]=='0')
			{
				st.x=i,st.y=j,st.s=1;
				q.push(st);
				b[i][j]=1;
				ans+=bfs();
				while(!q.empty())
				{
					q.pop();
				}
			}
		}
	}
	cout<<ans;
	return 0;
}
2023/7/1 14:25
加载中...