解題心得
在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;
}
