感觉没问题,结果8MLE+1TLE
查看原帖
感觉没问题,结果8MLE+1TLE
1122193
FarmerDrone楼主2024/5/14 22:35
#include <bits/stdc++.h> 
using namespace std;

inline int xy(int x, int y)
{
	return x * 10000 + y;
}

int x[4] = {0, 0, 1, -1};
int y[4] = {1, -1, 0, 0};

int main() 
{
//	freopen("P1746_1.in", "r", stdin);
	int n;
	cin >> n;
	bool m[n + 2][n + 2];
	int dis[n + 2][n + 2];
	for (int i = 0; i < n + 2; i++)
		for (int j = 0; j < n + 2; j++)
		{
			m[i][j] = 1;
			dis[i][j] = 99999999;
		}
	char ch;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> ch;
			m[i][j] = ch -'0';
		}
	int x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	dis[x1][y1] = 0;
	queue <int> q;
	q.push(xy(x1, y1));
	while (!q.empty())
	{
		if (q.front() == xy(x2, y2))
		{
			cout << dis[x2][y2];
			return 0;
		}
		for (int i = 0; i < 4; i++)
		{
			if (!m[q.front() / 10000 + x[i]][q.front() % 10000 + y[i]])
				if (dis[q.front() / 10000 + x[i]][q.front() % 10000 + y[i]] > dis[q.front() / 10000][q.front() % 10000])
				{
					dis[q.front() / 10000 + x[i]][q.front() % 10000 + y[i]] = dis[q.front() / 10000][q.front() % 10000] + 1;
					q.push(xy(q.front() / 10000 + x[i], q.front() % 10000 + y[i]));
				}
		}
		q.pop();
	}
	return 0;
}
2024/5/14 22:35
加载中...