bfs超时了,求助
  • 板块P1443 马的遍历
  • 楼主baking
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/15 22:49
  • 上次更新2023/10/28 06:30:05
查看原帖
bfs超时了,求助
405268
baking楼主2022/3/15 22:49
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

int n, m;
int xto[8] = { 1,2,2,1,-1,-2,-2,-1 };//上右开始
int yto[8] = { 2,1,-1,-2,-2,-1,1,2 };
struct node
{
	int x;
	int y;
	int step = 0;
}ini;

bool flag[410][410];



int main()
{
	cin >> n >> m;
	cin >> ini.x >> ini.y;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			memset(flag, 0, sizeof(flag));
			queue<node> q;
			q.push(ini);
			node temp;
			while (!q.empty())
			{
				temp = q.front();
				q.pop();
				if (temp.x == i && temp.y == j)
				{
					break;
				}
				for (int i = 0; i < 8; i++)
				{
					if (temp.x + xto[i] <= n && temp.x + xto[i] >= 1 && temp.y + yto[i] <= m && temp.y + yto[i] >= 1 && !flag[temp.x + xto[i]][temp.y + yto[i]])
					{
						q.push(node{ temp.x + xto[i],temp.y + yto[i],temp.step + 1 });
						flag[temp.x + xto[i]][temp.y + yto[i]] = 1;
					}
				}
			}
			if (temp.x == i && temp.y == j)
			{
				printf("%-5d", temp.step);
			}
			else
			{
				printf("%-5d",-1);
			}
		}
		printf("\n");
	}
}

样例5,9,10超时

2022/3/15 22:49
加载中...