3597487_ac_141ms_5260k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <queue>
#include <stdio.h>

using namespace std;

int dis[1010][1010];
char mud[1010][1010];

int n, x, y;

queue <int> que;
const int mov[][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

void bfs()
{
	int i;

	que.push(502);
	que.push(502);
	dis[502][502] = 0;
	while (dis[x][y] == -1)
	{
		int a = que.front();
		que.pop();
		int b = que.front();
		que.pop();
		for (i = 0; i < 4; i++)
		{
			int aa = a + mov[i][0];
			int bb = b + mov[i][1];
			if (aa < 0 || bb < 0 || aa > 1009 || bb > 1009 || mud[aa][bb] == '1' || dis[aa][bb] != -1)
			{
				continue;
			}
			que.push(aa);
			que.push(bb);
			dis[aa][bb] = dis[a][b] + 1;
		}
	}
	printf("%d\n", dis[x][y]);
}

int main()
{
	int i, j, a, b;

	scanf("%d%d%d", &x, &y, &n);
	x += 502;
	y += 502;
	for (i = 0; i < 1010; i++)
	{
		for (j = 0; j < 1010; j++)
		{
			mud[i][j] = '0';
			dis[i][j] = -1;
		}
	}
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &a, &b);
		a += 502;
		b += 502;
		mud[a][b] = '1';
	}
	bfs();
	return 0;
}