BFS为啥WA这么多...是我nm搞反了吗...求助
查看原帖
BFS为啥WA这么多...是我nm搞反了吗...求助
13805
Ackoter楼主2020/7/25 20:28
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<list>
#include<map>
using namespace std;
struct point{
	int x,y,len;
}fi,p[180001];
int dp[151][151],a[151][151],l,r,n,m;
const int gx[4]={0,0,-1,1},gy[4]={-1,1,0,0};
void BFS()
{
	l=r=1;
	p[1]=fi;
	while(l<=r)
	{
		if(a[p[l].x][p[l].y]) dp[p[l].x][p[l].y]=0,p[l].len=0; else dp[p[l].x][p[l].y]=min(dp[p[l].x][p[l].y],min(min(dp[p[l].x+1][p[l].y],dp[p[l].x-1][p[l].y]),min(dp[p[l].x][p[l].y+1],dp[p[l].x][p[l].y-1]))+1);
		for(int i=0;i<4;i++)
		{
			if(p[l].x+gx[i]>n||p[l].x+gx[i]<1||p[l].y+gy[i]>m||p[l].y+gy[i]<1) continue;
			if(dp[p[l].x][p[l].y]+1>=dp[p[l].x+gx[i]][p[l].y+gy[i]]) continue;
			p[++r].x=p[l].x+gx[i];p[r].y=p[l].y+gy[i];p[r].len=p[l].len+1;
		}
		l++;
	}
}
int main()
{
	memset(dp,0x3f,sizeof(dp));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]&&!fi.x) fi.x=i,fi.y=j;
		}
	BFS();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",dp[i][j]);
		printf("\n");
	}
	return 0;
}
2020/7/25 20:28
加载中...