老wa,求解
查看原帖
老wa,求解
544711
xiaofeng667788楼主2021/8/5 08:58
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;

char map[N][N];
int d[N][N], ti[N][N], st[N][N];
int t, n, m, x1, x2, yy, y2, rx, ry, flag;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs_f()
{
	memset(st, 0, sizeof st);
	ti[x2][y2] = 0;
	queue<PII> q;
	q.push({x2, y2});
	
	while (!q.empty())
	{
		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 >= 0 && y >= 0 && x < n && y < m && map[x][y] != '#' && ti[x][y] == -1 && st[x][y] == 0)
			{
				st[x][y] = 1;
				q.push({x, y});
				ti[x][y] = ti[t.first][t.second] + 1;
			}
		}
	}
}

void bfs()
{
	memset(st, 0, sizeof st);
	d[x1][yy] = 0;
	queue<PII> q;
	q.push({x1,yy});
	while (!q.empty())
	{
		PII t = q.front();
		q.pop();
		for (int i = 0; i < 4; i ++ )
		{
			int x = dx[i] + t.first;
			int y = dy[i] + t.second;
			if (x >= 0 && y >= 0 && x < n && y < m && d[t.first][t.second] + 1 < ti[x][y] && map[x][y] == '.' && st[x][y] == 0)
			{
				st[x][y] = 1;
				d[x][y] = d[t.first][t.second] + 1;
				q.push({x, y});
				if (x == 0 || y == 0 || x == n - 1 || y == m - 1)
				{
					rx = x;
					ry = y;
					flag = 1;
					break;
				}
			}
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t -- )
	{
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i ++ )
			scanf("%s", map[i]);
		
		memset(d, -1, sizeof d);
		memset(ti, -1, sizeof ti);
		flag = 0;
		for (int i = 0; i < n; i ++ )
			for(int j = 0; j < m; j ++ )
			{
				if (map[i][j] == 'J')
				{
					x1 = i;
					yy = j;
				}
				if (map[i][j] == 'F')
				{
					x2 = i;
					y2 = j;
				}
			}
		if (x1 == 0 || yy == 0 || x1 == n - 1 || yy == m - 1)
		{
			cout << 1 << endl;
			continue;
		}
		else
		{
			bfs_f();
			bfs();
			if (flag == 0) cout << "IMPOSSIBLE" << endl;
			else cout << d[rx][ry] + 1 << endl;
		}
	}
	return 0;
}
2021/8/5 08:58
加载中...