d406: 倒水時間

解題心得

在dfs的「探索相鄰節點」步驟除了一一列舉外，還有更簡潔的寫法，就是將座標所需的位移裂成矩陣，迴圈檢查合法與否即可。

程式碼

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

int map[101][101] = { 0 };
struct Point
{
	int x, y, step = -1;
};

int main()
{
	int s, n, m, counter = 1;
	while (cin >> s)
	{
		cin >> n >> m;
		bool isVisited[101][101] = { false };
		Point start, now;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> map[i][j];
				if (i == 0 && map[i][j] == 1)
					start.x = i, start.y = j;
			}
		}
		queue<Point> q;
		isVisited[start.x][start.y] = true;
		start.step = 1;
		q.push(start);
		int dx[4] = { 1,0,0,-1 }, dy[4] = { 0,1,-1,0 }; // 最後一個是往上
		while (!q.empty())
		{
			now = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				if (i == 3 && s == 2) break;
				Point p;
				p.x = now.x + dx[i]; p.y = now.y + dy[i];
				if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m && map[p.x][p.y] != 0 && !isVisited[p.x][p.y])
				{
					isVisited[p.x][p.y] = true;
					p.step = now.step + 1;
					map[p.x][p.y] = p.step;
					q.push(p);
				}
				
			}
			isVisited[now.x][now.y] = true;
		}
		cout << "Case " << counter++ << ":" << endl;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] != 0 && !isVisited[i][j]) cout << 0;
				else cout << map[i][j];
				if (j != m - 1) cout << " ";
				else cout << endl;
			}
		}
	}
	return 0;
}