我們討論的是《戰爭之城》的一個簡單版本。如果地圖上只有空曠的空間，河流，鋼墻和磚墻。你的任務是盡快得到獎金，假設沒有敵人會打擾你(見下圖)

你的坦克不能穿過河流和墻壁，但它可以通過射擊摧毀磚墻。當你擊中磚墻時，磚墻會變成空地，但是，如果你的子彈擊中了鋼墻，就不會對墻造成損傷。在每一個轉彎中，你可以選擇移動到一個相鄰的(4個方向，而不是8個)空曠的地方，或者不移動地朝四個方向中的一個射擊。射擊會朝那個方向進行，直到它超出地圖范圍或者撞到墻上。如果子彈擊中了一堵磚墻，這堵墻就會消失(也就是說，在這個回合中)。根據地圖的描述，你的坦克和目標的位置，你至少要轉多少圈才能到那里？

【輸入】
輸入由幾個測試用例組成。每個測試用例的第一行包含兩個整數 m 和 n (2 < = m，n < = 300)。每一行包含 n 個大寫字母，每個字母分別是“ y”(you)、“ t”(target)、“ s”(steel wall)、“ b”(brick wall)、“ r”(river)和“ e”(empty space)。“ y”和“ t”都只出現一次。測試用例 m = n = 0表示輸入的結束，并且不應該被處理。對于每個測試用例，

【輸出】
請至少在單獨的行中輸出您的方式。如果你不能到達目標，輸出“-1”代替。

【樣例輸入】
3 4
YBEB
EERE
SSTE
0 0

【樣例輸出】
8

---

分析：

實驗題， 可能要答辯， 所以我盡量寫得詳細點， 喜歡的請點個贊哦 謝謝！

將迷宮輸入 （代碼46-51）， 同時判斷， 如果為Y， 則記錄為開始點(49行)， 如果為T，則記錄為結束點(50行)

vis數組的作用是查看該點是否已經走過， 走過的點置1， 沒走過的點置0， 因此開始點置1(52)

進行dfs深搜(54)

轉到dfs函數， （10）

首先定義next數組， 分別表示向上下左右各走一個格。 （11）

定義邊界條件： 如果到達T字符處，則證明走到終點，更新最短路徑(19)

接下來開始循環，枚舉四種走法， 首先記錄下一個點的坐標， 接下來判斷是否越界， 再然后判斷是否是障礙物(鋼鐵或河流)或者已經在路徑中。 如果符合條件， 則跳到這個點， 基于這個點繼續深搜， 不過要注意的是， 如果為B字符， step需要+2(開炮+走路)， 如果是E或T就+1

結束，輸出。

---

代碼展示

#include<cstdio> #include<iostream> using namespace std;int startx, starty, finshx, finshy; int n, m, Min = 0x3f3f3f3f; char a[305][305]; int vis[305][305];void dfs(int x, int y, int step) {int next[4][2] = {{0, 1}, //向右走 {1, 0}, //向下走{0, -1}, //向左走 {-1, 0}}; //向上走 int tx, ty, k;//邊界條件， 是否達到targetif(a[x][y] == 'T') {//更新最小值if(step < Min) Min = step;return ; } //枚舉四種走法for(k = 0; k <= 3; k++) { //右下左上 //計算下一個點的坐標tx = x + next[k][0]; ty = y + next[k][1];//判斷是否越界if(tx<0 || tx>=n || ty<0 || ty>=m) continue;//判斷是否為障礙物或者已經在路徑中if(a[tx][ty]!='S' && a[tx][ty]!='R' && !vis[tx][ty]) {vis[tx][ty] = 1;if(a[tx][ty] == 'B') dfs(tx, ty, step+2);else if(a[tx][ty] == 'E' || a[tx][ty] == 'T') dfs(tx, ty, step+1);vis[tx][ty] = 0;} } return; }int main() {while(cin>>n>>m && n) {for(int i = 0; i < n; i++) //1、輸入 for(int j = 0; j < m; j++) {cin>>a[i][j];if(a[i][j] == 'Y') startx = i, starty = j;if(a[i][j] == 'T') finshx = i, finshy = j;}vis[startx][starty] = 1;dfs(startx, starty, 0);//輸出最短步數 cout << Min << '\n'; } return 0; }

---

發現光，追隨光，成為光，發散光。

總結

以上是生活随笔為你收集整理的我们讨论的是《战争之城》的一个简单版本。如果地图上只有空旷的空间，河流，钢墙和砖墙。你的任务是尽快得到奖金，假设没有敌人会打扰你(见下图) 你的坦克不能穿过河流和墙壁，但它可以通过射击摧毁砖墙。当你击的全部內容，希望文章能夠幫你解決所遇到的問題。

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