用vector优化后爆零全WA,求助
查看原帖
用vector优化后爆零全WA,求助
795542
LoveYuigahamaYui楼主2024/7/12 15:53
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII; 
const int N = 16400;
int n, m, ex, ey, res = 1e9;
string c[N];
vector <int> d[N]; 
bool flag;
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int ddx[] = {0, 0, 1, 1, 1, -1, -1, -1};
int ddy[] = {1, -1, -1, 0, 1, -1, 0, 1};

void bfs(int sx, int sy)
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			d[i][j] = 1e9;
		}
	}
	queue <PII> q;
	q.push({sx, sy});
	d[sx][sy] = 0;
	while (q.size())
	{
		PII t = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int x = t.first + dx[i];
			int y = t.second + dy[i];
			if (x >= 1 && x <= n && y >= 1 && y <= m && d[x][y] == 1e9 && c[x][y] == 'O')
			{
				d[x][y] = d[t.first][t.second] + 1;
//				cout<<x<<" "<<y<<" "<<d[x][y]<<"\n";
				q.push({x, y});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> c[i];
		d[i].resize(m+1);
	}
	int sx, sy;
	while (true)
	{
		cin >> ex >> ey >> sx >> sy;
		if (sx == 0 && sy == 0 && ex == 0 && ey == 0) return 0;
		bfs(sx, sy);
		res = d[ex][ey];
		for (int i = 0; i < 8; ++i)
		{
			int x = ex, y = ey;
			while (x + ddx[i] >= 1 && x + ddx[i] <= n && y + ddy[i] >= 1 && y + ddy[i] <= m && c[x + ddx[i]][y + ddy[i]] == 'O')
			{
				x += ddx[i];
				y += ddy[i];
				res = min(res, d[x][y]);
			}
		}	
//		for (int i = 1; i <= n; ++i)
//		{
//			for (int j = 1; j <= m; ++j)
//			{
//				cout << d[i][j] << ' ';
//			}
//			cout << endl;
//		}
		if (res == 1e9) cout << "Poor Harry" << endl;
		else cout << res << endl;		
//		cout << res << endl;
	}
	return 0;
}
2024/7/12 15:53
加载中...