題意：從s處出發，每次可以往東南西北4個方向之一前進。如果前方有墻壁，可以把墻壁往前推一格。如果有兩堵墻或者多堵墻，則不能移動，另外也不能推邊上的墻。找出最短路徑。

分析：剛拿到題目肯定想到是bfs，但是由于地圖較大，bfs超時

#include<iostream> #include<time.h> #include<queue> #include<stdlib.h> #include<string.h> using namespace std; struct node {int r, c;int ans=0;int map[10][10];char route[100]; }; int direction[] = { 1,2,4,8 }; int dr[] = { 0,-1,0,1 }; int dc[] = { -1,0,1,0 }; char rr[] = { 'W','N','E','S' }; int row, col; int mp[10][10]; void bfs() {queue<node> q;node t;t.r = row; t.c = col;t.ans = 0;memcpy(t.map, mp, sizeof(mp));q.push(t);while (!q.empty()) {t = q.front();q.pop();if (t.r < 1 || t.r>4 || t.c < 1 || t.c>6) {for (int j = 0; j < t.ans; j++) {cout << t.route[j];}cout << endl;return;}row = t.r; col = t.c;for (int i = 0; i < 4; i++) {node temp;temp.ans = t.ans;memcpy(temp.map, t.map, sizeof(t.map));memcpy(temp.route, t.route, sizeof(t.route));int ddr = row, ddc = col;ddr += dr[i];ddc += dc[i];if ((temp.map[row][col] & direction[i])){if (ddr >= 1 && ddr <= 4 && ddc >= 1 && ddc <= 6) {if (temp.map[ddr][ddc] & direction[i])continue;//前方有墻else {int k = i; k ^= 2;temp.map[row][col] ^= direction[i];//-temp.map[ddr][ddc] ^= direction[i];//+temp.map[ddr][ddc] ^= direction[k];//-temp.map[ddr + dr[i]][ddc + dc[i]] ^= direction[k];//+}}else continue;//有墻且越界}temp.route[temp.ans++]= rr[i];temp.r = ddr; temp.c = ddc;q.push(temp);}}} int main() {while (cin >> col >> row&&col&&row) {memset(mp, 0, sizeof(mp));for (int i = 1; i <= 4; i++)for (int j = 1; j <= 6; j++)cin >> mp[i][j];bfs();}return 0; }

后來用了佚代加深：

#include<iostream> #include<time.h> #include<queue> #include<stdlib.h> #include<string.h> using namespace std; int direction[] = { 1,2,4,8 }; int dr[] = { 0,-1,0,1 }; int dc[] = { -1,0,1,0 }; char rr[] = { 'W','N','E','S' }; int row, col; int maxd; int vis[10][10]; int map[10][10]; char route[100]; bool solve(int r,int c,int dep,int dir) {if (dep >= maxd)return false;for (int i = 0; i < 4; i++) {if (dir!=-1&&i == dir)continue;int ddr = r, ddc = c;ddr += dr[i];ddc += dc[i];if ((map[r][c] & direction[i])){if (ddr >= 1 && ddr <= 4 && ddc >= 1 && ddc <= 6) {if (map[ddr][ddc] & direction[i])continue;//前方有墻else {int k = i; k ^= 2;map[r][c] ^= direction[i];//-map[ddr][ddc] ^= direction[i];//+map[ddr][ddc] ^= direction[k];//-map[ddr + dr[i]][ddc + dc[i]] ^= direction[k];//+route[dep] = rr[i];if (solve(ddr, ddc, dep + 1,i^2))return true;map[r][c] ^= direction[i];//-map[ddr][ddc] ^= direction[i];//+map[ddr][ddc] ^= direction[k];//-map[ddr + dr[i]][ddc + dc[i]] ^= direction[k];//+}}else continue;//有墻且越界}else {if (ddr < 1 || ddr>4 || ddc < 1 || ddc>6) {for (int j = 0; j < dep; j++) {cout << route[j];}cout <<rr[i]<< endl;return true;}route[dep] = rr[i];if (solve(ddr, ddc, dep + 1, i ^ 2))return true;}}return false; } int main() {while (cin >> col >> row&&col&&row) {for (int i = 1; i <= 4; i++)for (int j = 1; j <= 6; j++)cin >> map[i][j];for (maxd = 1;; maxd++) {if (solve(row,col,0,-1))break;}}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 10384The Wall Pushers推门游戏（迭代加深）的全部內容，希望文章能夠幫你解決所遇到的問題。

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