itdef

https://vjudge.net/problem/POJ-3009

在 MM-21 星球上，今年的奧運會之后，冰壺運動開始流行起來。但規則與我們的有些不同。冰壺比賽是在一塊冰板上進行的，冰板上標有方形網眼。
他們只使用一塊石頭。游戲的目的是用最少的步數將石頭從起點引向終點。

圖 1 顯示了游戲棋盤的一個示例。一些方格可能被積木占據。有兩個特殊的方格，即起點和目標方格，這兩個方格沒有積木。(這兩個方格是不同的。）
一旦棋子開始移動，它就會一直走下去，直到碰到一個積木為止。為了讓石子到達目標，你可能需要讓石子停下來，撞上一個木塊，然后再扔一次。


圖 1：棋盤示例（S：起點，G：終點）

石子的移動遵循以下規則：

開始時，石子靜止在起點方格。
石子的移動僅限于 x 和 y 方向。禁止對角線移動。
當石塊靜止不動時，您可以通過投擲使其移動。您可以將它扔向任何方向，除非它立即被擋住（圖 2(a)）。
投擲后，石子會一直向同一方向移動，直到出現以下情況之一：
石子擊中一個木塊（圖 2(b)、(c)）。
石塊停在被擊中石塊旁邊的方格。
木塊消失。
棋子離開棋盤。
游戲以失敗告終。
石子到達目標方格。
石子停在目標方格，游戲以成功結束。
一局游戲中投擲石塊的次數不能超過 10 次。如果石子在 10 次移動中沒有到達目標位置，則游戲以失敗告終。

圖 2：石子移動

根據規則，我們想知道石頭在開始時是否能到達目標，如果能，則需要最少的移動次數。

按照圖 1 所示的初始配置，需要走 4 步棋才能將石子從起點帶到終點。路線如圖 3(a) 所示。注意，當棋子到達終點時，棋盤的配置發生了變化，如圖 3(b)所示。


輸入是一系列數據集。輸入結束時，會出現一行包含兩個 0 的空格。數據集的數量永遠不會超過 100 個。

每個數據集的格式如下。

電路板的寬度（=w）和高度（=h）
棋盤第一行
...
棋盤的第 h 行

黑板的寬度和高度滿足以下條件： 2 <= w <= 20，1 <= h <= 20。

每行由 w 個十進制數字組成，以空格分隔。數字描述了相應方格的狀態。

0 空方格
1 塊
2 開始位置
3 目標位置

The dataset for Fig. D-1 is as follows:

6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1

輸出
對于每個數據集，打印一行十進制整數，表示從起點到目標的最小移動次數。如果沒有這樣的路線，則打印-1。每一行中除該數字外不得有任何其他字符。


輸入
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
14 6
0 0 1 0 0 0 0 1 1 0 1 1 1 0
0 0 1 0 1 0 1 1 1 1 1 1 1 1
1 1 0 2 1 1 0 0 1 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 0 1 1 0 1 1 0 0 0
1 0 1 0 0 1 0 0 1 0 0 0 0 3
4 8
0 1 0 0
0 0 0 0
1 0 0 1
0 0 0 0
0 0 0 0
3 0 1 0
1 0 1 0
1 0 0 2
0 0

輸出
1
4
-1
4
10
-1

根據題意
本來可以考慮使用BFS 查看10回合以內覆蓋的范圍。
但是每次移動后，碰到冰壁會損壞墻壁，狀態是變化的。BFS不方便記錄。
所以 考慮DFS10回合內的所有移動，更加方便。
注意兩點
1 通過目標位置即可 不用停留在目標位置上
2 緊貼墻壁不能向墻壁方向前進 需要有空地加速
代碼如下

#include <iostream>
#include <queue>
#include <cstring>

//https://vjudge.net/problem/POJ-3009

using namespace std;

const int N = 22;
int gra[N][N];
int w, h, startx, starty;
int ans = 0x3f3f3f3f;

void dfs(int x, int y, int step);
void change(int x, int y, int addx, int addy, int step) {
	int newx = x + addx; int newy = y + addy;

	if (newx >= 0 && newx < h && newy >= 0 && newy < w && gra[newx][newy] == 1) {
		//不能往這個方向移動 
		return;
	}

	if (newx < 0 || newx >= h || newy < 0 || newy >= w) {
		//滑出街 不能移動
		return;
	}

	x += addx, y += addy;
	//開始滑動
	while (x >= 0 && x < h && y >= 0 && y < w) { 
		if (gra[x][y] == 3) {
			ans = min(step+1, ans);
			return;
		}
		else if (gra[x][y] == 1) {
			gra[x][y] = 0;
			dfs(x-addx, y-addy, step + 1);
			gra[x][y] = 1;  return;
		}
		x += addx, y += addy;
	}
}

void dfs(int x, int y, int step) {
	//向四個方向滑動
	if (step > 10) return;

	change(x, y, 0, 1, step);
	change(x, y, 0, -1, step);
	change(x, y, 1, 0, step);
	change(x, y, -1, 0, step);

	return ;
}

void solve() {
	ans = 0x3f3f3f3f;
	dfs(startx,starty,0);

	if (ans > 10) ans = -1;
	cout << ans << endl;
}

int main() {
	while (cin >> w >> h) {
		if (w == 0 && h == 0)break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> gra[i][j];
				if (gra[i][j] == 2) {
					startx = i; starty = j;
				}
			}
		}

		solve();
	}


	return 0;
}

我的視頻題解空間