BFS 60pts,TLE了
查看原帖
BFS 60pts,TLE了
542893
tiaotiao0830楼主2023/5/14 10:03
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

int ans[405][405],visited[405][405];
int dx[] = {-2,-1,1,2,2,1,-1,-2};
int dy[] = {-1,-2,-2,-1,1,2,2,1};
struct Node
{
	int x;
	int y;
	int steps; 
};
Node tnode,pnode;
queue<Node> qlist;

void bfs(int sx,int sy,int fx,int fy,int n,int m)
{	
	tnode.x = sx;
	tnode.y = sy;
	tnode.steps = 0;
	visited[sx][sy] = 1;
	qlist.push(tnode);
	
	while(!qlist.empty())
	{
		tnode = qlist.front();
		qlist.pop();
		
		for(int i = 0;i < 8;i++)
		{	
			if(tnode.x == fx && tnode.y == fy)
			{
				 ans[fx][fy] = tnode.steps;
			}
			
			if(tnode.x + dx[i] < 1
			|| tnode.x + dx[i] > n
			|| tnode.y + dy[i] < 1
			|| tnode.y + dy[i] > m)
			{
				continue;
			}
			if(visited[tnode.x + dx[i]][tnode.y + dy[i]] == 1)
			{
				continue;
			}
			
			pnode.x = tnode.x + dx[i];
			pnode.y = tnode.y + dy[i];
			visited[pnode.x][pnode.y] = 1;
			pnode.steps = tnode.steps + 1; 
			qlist.push(pnode);
		}
	}
}

int main()
{
	int n,m,x,y;
	cin >> n >> m >> x >> y; 
	visited[x][y] = 1;
	memset(ans,-1,sizeof(ans));
	
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			memset(visited,0,sizeof(visited));
			bfs(x,y,i,j,n,m);
		}
	}
	
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
2023/5/14 10:03
加载中...