在很多 RPG (Role-playing Games) 游戲中,迷宮往往是非常復雜的游戲環節。通常來說,我們在走迷宮的時候都需要花非常多的時間來嘗試不同的路徑。但如果有了算法和計算機的幫助,我們能不能有更快的方式來解決這個問題?我們可以進行一些嘗試。
現在我們有一個 N 行 M 列的迷宮。迷宮的每個格子如果是空地則可以站人,如果是障礙則不行。在一個格子上,我們可以一步移動到它相鄰的 8 個空地上,但不能離開地圖的邊界或者跨過兩個障礙的夾縫。下圖是一個移動規則的示例。
為了離開迷宮,我們還需要觸發迷宮中所有的機關。迷宮裡總共有 K 個機關,每個機關都落在一個不同的空地上。如果我們到達了某個機關所在的格子時,這個機關就會被自動觸發,並在觸發之後立即消失。我們的目標是按順序觸發所有的 K 個機關,而當最後一個機關被觸發時,我們就可以離開迷宮了。
現在我們已經拿到了迷宮地圖,並且知道所有障礙、機關的位置。初始時我們位於迷宮的某個非障礙格子上,請你計算我們最少需要移動多少步才能離開迷宮?
輸入的第一行是測試數據的組數 T (T ≤ 20)。
對於每組測試數據:第一行包含地圖的行數 N (2 ≤ N ≤ 100),列數 M(2 ≤ M ≤ 100) 和機關的數量 K(1 ≤ K ≤10)。接下來 N 行,每行包含 M 個字符,其中字符 ‘#’ 表示障礙,而 ‘.’ 表示空地。接下來一行描述了我們的初始位置 (x, y),表示我們一開始在第 x 行第 y 列的格子上。這個格子保證是個空地。接下來 K 行,每行給出了一個機關的位置。所有的機關都不會出現在障礙上,並且任意兩個機關不會出現在同一個空地上。我們需要按輸入給定的順序觸發所有的 K 個機關。
對於每組測試數據,輸出離開迷宮所需要的最少步數。如果無論如何都不能離開迷宮,輸出 -1。
#include#include #include #include using namespace std; const int maxn = 110; const int inf = 0x3f3f3f3f; const int dir[][2] = {0, 1, 0, -1, -1, 0, 1, 0, 1, 1, 1, -1, -1, 1, -1, -1}; char G[maxn][maxn]; bool vis[maxn][maxn]; int N, M, K; // N rows int sx, sy, tx, ty; vector vec; struct Node { int x, y, step; }; void getMap() { int i, j, x, y; for (i = 1; i <= N; ++i) scanf("%s", G[i] + 1); scanf("%d%d", &sx, &sy); vec.clear(); for (i = 0; i < K; ++i) { cin >> x >> y; G[x][y] = '@'; vec.push_back(x); vec.push_back(y); } } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int abs(int x) { return x < 0 ? -x : x; } bool check(int x, int y) { return x > 0 && x <= N && y > 0 && y <= M && !vis[x][y] && G[x][y] != '#' && G[x][y] != '@'; } int BFS() { if (G[sx][sy] == '@') return -inf; Node u, v; int i, j; u.x = sx; u.y = sy; u.step = 0; queue Q; Q.push(u); memset(vis, 0, sizeof(vis)); while (!Q.empty()) { u = Q.front(); Q.pop(); if (u.x == tx && u.y == ty) return u.step; for (i = 0; i < 8; ++i) { v = u; v.x += dir[i][0]; v.y += dir[i][1]; ++v.step; if (abs(u.x - v.x) + abs(u.y - v.y) == 2) { int cnt = 0; int x1 = min(u.x, v.x); int y1 = min(u.y, v.y); int x2 = max(u.x, v.x); int y2 = max(u.y, v.y); if (G[x1][y1] == '#') ++cnt; if (G[x1][y2] == '#') ++cnt; if (G[x2][y1] == '#') ++cnt; if (G[x2][y2] == '#') ++cnt; if (cnt >= 2) continue; } if (check(v.x, v.y)) { vis[v.x][v.y] = true; Q.push(v); } } } return -inf; } void solve() { int ret = 0, i; for (i = 0; i < vec.size(); ) { tx = vec[i++]; ty = vec[i++]; G[tx][ty] = '.'; ret += BFS(); if (ret < 0) { ret = -1; break; } sx = tx; sy = ty; } cout << ret << endl; } int main() { int T; cin >> T; while (T--) { cin >> N >> M >> K; getMap(); solve(); } return 0; }