前置技能

無

解說

你還在用 if 拓展 BFS 的每一步嗎？

除了重覆的 code 增加、複製貼上改錯的 bug 率上升，
code也會變長、變得混亂難讀。

為此，用陣列預存每一步的變化，會讓事情變得單純許多：

// 定義上下左右移動
// 上下左右對應到平面座標後，剛好角度是 0, 90, 180, 270
// 用 cos 0, 90, 180, 270 和 sin 0, 90, 180, 270 來建表，節省思考時間又不易錯
// 反正應該都背過 sin/cos 在這四個特殊角的值吧 (?
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// 轉移
for (int k=0; k<4; k++)
{
    tx = x + dx[k];
    ty = y + dy[k];
    if (valid(tx, ty) && !used[tx][ty])
    {
        ...
    }
}

斜角移動或三維迷宮依此類推。

延伸

同理，可拓展到任何一對一映射變換的題目，
例如 UVa 11959 Dice 的骰子翻轉：

// tbl[i] 為第 i 組的變換
// tbl[i][j] = k 表示第 j 格會是原本的第 k 格
int tbl[6][6] = {
	{0, 1, 2, 3, 4, 5}, 
	{1, 0, 5, 4, 3, 2}, 
	{2, 4, 1, 3, 0, 5}, 
	{3, 5, 2, 1, 4, 0}, 
	{4, 2, 0, 3, 1, 5}, 
	{5, 3, 2, 0, 4, 1}
};

我們以 {1, 0, 5, 4, 3, 2} 這組作例子，實際上是這樣：

  idx 0 idx 1 idx 2 idx 3 idx 4 idx 5
原本 dice[0] dice[1] dice[2] dice[3] dice[4] dice[5]
目標 dice[1] dice[0] dice[5] dice[4] dice[3] dice[2]