d453: 三、最短距離

解題心得

也是中規中矩的bfs(?

記得清空，以及題目input的座標是從1開始。

程式碼

#include <iostream>
#include <queue>
using namespace std;

struct Point
{
	int x, y, step = -1;
};
char map[101][101] = { 0 };
bool isVisited[101][101] = { false };
int main()
{
	int N, n, m;
	Point start, end, now;
	cin >> N;
	while (N--)
	{
		cin >> n >> m >> start.x >> start.y >> end.x >> end.y;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> map[i][j];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				isVisited[i][j] = false;
		start.x -= 1; start.y -= 1; end.x -= 1; end.y -= 1;
		//bfs
		queue<Point> q;
		isVisited[start.x][start.y] = true; start.step = 1;
		bool isValid = false;
		q.push(start);
		while (!q.empty())
		{
			now = q.front(); 
			q.pop();
			//cout << now.x << " " << now.y << " " << now.step << endl;
			if (now.x == end.x && now.y == end.y)
			{
				cout << now.step << endl;
				isValid = true;
				break;
			}
			if (now.x - 1 >= 0 && map[now.x - 1][now.y] == '0' && !isVisited[now.x - 1][now.y])
			{
				Point p; p.x = now.x - 1; p.y = now.y; 
				isVisited[now.x - 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.x + 1 < n && map[now.x + 1][now.y] == '0' && !isVisited[now.x + 1][now.y])
			{
				Point p; p.x = now.x + 1; p.y = now.y;
				isVisited[now.x + 1][now.y] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y - 1 >= 0 && map[now.x][now.y - 1] == '0' && !isVisited[now.x][now.y - 1])
			{
				Point p; p.x = now.x; p.y = now.y - 1;
				isVisited[now.x][now.y - 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			if (now.y + 1 < m && map[now.x][now.y + 1] == '0' && !isVisited[now.x][now.y + 1])
			{
				Point p; p.x = now.x; p.y = now.y + 1;
				isVisited[now.x][now.y + 1] = true;
				p.step = now.step + 1;
				q.push(p);
			}
			isVisited[now.x][now.y] = true;
		}
		if (!isValid) cout << 0 << endl;
	}
	return 0;
}