題目描述

伯羅奔尼撒戰爭是以雅典為首的提洛同盟與以斯巴達為首的伯羅奔尼撒聯盟之間的一場戰爭。這場戰爭從前431年一直持續到前404年，使得絕大多數周邊城邦必須加入其中一方的陣營。戰爭第一階段（BC431-BC421），雅典在伯里克利的領導之下，憑借強大的海軍，采取陸地上防御在海上進攻的策略。而斯巴達在阿基達摩斯二世的領導之下，率領它令人畏懼的戰士進行陸地強攻。兩個強邦側重點不同的軍事力量導致了戰爭第一階段的僵持局面。
話說，有一天阿基達摩斯二世決定率兵進攻雅典的一個居民點阿提卡，當他們滿懷斗志的奔向阿提卡的時候，殊不知他們正走向伯利克里所設下的迷宮陷阱之中。當他們發現時，已為時已晚。
As you know, the Magpie Festival is comging!
為了早日返回斯巴達，阿基達摩斯二世立即讓所有的斯巴達勇士去需找迷宮的出口E。現在他們被困在迷宮的S點，迷宮中“.”表示空地，可以通過，“#”表示墻，不能通過，每次只能向上下左右四個方向移動，每移動一個單位距離需要耗費一個單位時間，所有斯巴達勇士的移動速度相同。現在請你計算一下他們最短需要多少時間才能找到迷宮的出口。
PS：假設迷宮中每個點可以容納的人數沒有限制，每個斯巴達勇士的行動方向之間沒有影響。

輸入格式

第一行有一個整數t(0=<t<=100)，代表有t組測試數據。
每組測試數據第一行輸入三個數n,m, c,(2=<m<=n<=500,100=<c<=10000)分別代表迷宮的長度和寬度，以及被困迷宮的斯巴達勇士數（不包括阿基達摩斯二世）。下面m行每行有n個字符用來表示迷宮地圖。詳細輸入格式見樣例。

輸出

輸出一個整數，表示找到迷宮出口的最短時間，每組輸出占一行。如不能找到出口輸入-1

樣例輸入

1
5?5?100
#####
#S..#
#...#
#...E
#####

樣例輸出

5

#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include <queue> using namespace std; struct Pos {int x, y, time; }; const int N = 1000 + 10; int n, m, c, sx, sy, vis[N][N]; char maze[N][N]; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int judge(int x, int y) {if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] != '#')return 1;return 0; } int dfs(int x, int y) {Pos a, t;queue <Pos> q;a.x = x, a.y = y, a.time = 0;vis[x][y] = 1;q.push(a);while (!q.empty()){a = q.front();q.pop();if(maze[a.x][a.y] == 'E')return a.time;for(int i = 0; i < 4; ++i){t.x = a.x + dir[i][0];t.y = a.y + dir[i][1];t.time = a.time + 1; //訪問到點 t 是所用的時間if(judge(t.x, t.y)) //判斷下個點是否可以訪問，若可以則加入隊列{vis[t.x][t.y] = 1;q.push(t);}}}return -1; } int main() {int t;cin >> t;while (t--){memset(vis, 0, sizeof(vis)); //清空標記數組cin >> n >> m >>c;for(int i = 0; i < m; ++i){cin >> maze[i];for(int j = 0; j < n; ++j){if(maze[i][j] == 'S') //判斷起點{sx = i;sy = j;}}}cout << dfs(sx, sy) << endl;}return 0; }

總結

以上是生活随笔為你收集整理的DFS【古希腊之争（一）】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。