4234637_ac_125ms_1084k.cc

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

#include <queue>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define MAX 310

using namespace std;

int matrix[MAX][MAX];
const int mov[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int visited[MAX][MAX];

bool valid(int x, int y)
{
	return x >= 0 && x <= MAX && y >= 0 && y <= MAX;
}

struct Node
{
	int x, y, t;

	Node (int x, int y, int t)
	{
		this->x = x;
		this->y = y;
		this->t = t;
	}
};

int bfs()
{
	queue <Node> q;

	if (matrix[0][0] == 0)
	{
		return -1;
	}
	if (matrix[0][0] == -1)
	{
		return 0;
	}
	memset(visited, 0, sizeof visited);
	q.push(Node (0, 0, 0));
	visited[0][0] = 1;
	while (!q.empty())
	{
		Node t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x, y;
			x = t.x + mov[i][0];
			y = t.y + mov[i][1];
			if (valid(x, y) && !visited[x][y])
			{
				if (matrix[x][y] == -1)
				{
					return t.t + 1;
				}
				if (matrix[x][y] > t.t + 1)
				{
					visited[x][y] = 1;
					q.push(Node(x, y, t.t + 1));
				}
			}
		}
	}
	return -1;
}

int main()
{
	int n;
	int x, y, t;

	memset(matrix, -1, sizeof matrix);

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &x, &y, &t);
		if (matrix[x][y] == -1 || matrix[x][y] > t)
		{
			matrix[x][y] = t;
		}
		for (int j = 0; j < 4; j++)
		{
			int nx, ny;
			nx = x + mov[j][0];
			ny = y + mov[j][1];
			if (valid(nx, ny) && (matrix[nx][ny] == -1 || matrix[nx][ny] > t))
			{
				matrix[nx][ny] = t;
			}
		}
	}
	printf("%d\n", bfs());
	return 0;
}