機器人要在一個矩形迷宮里行動（不能原地停留，只能走向上/下/左/右），每移動一格花費1個單位時間。


迷宮有以下幾種元素：
【*】 機器人的起點
【#】 墻。機器人不能走過這些格子
【.】 平地。機器人可以在上面自由行走
【0-9】 寶藏。當機器人走到此處會立刻獲得該數(shù)字相應的寶藏，寶藏不會消失，可以反復獲取（但不能停留）

若機器人要恰好獲得總和為x的寶藏，它最少需要多少時間？

先是用DFS做了一次，案例過了，提交爆內(nèi)存，數(shù)據(jù)過大明顯DFS不行 ?還是貼一下代碼 ?

#include<stdio.h> #include<string.h> //爆內(nèi)存 char map[2000][2000]; int dir[4][2]={-1,0,0,-1,1,0,0,1}; int n,m,t,sum; int use[2000][2000]; void DFS(int x,int y,int time,int money) {if(money==sum){if(time<t)t=time;}if(money>sum)return;for(int i=0;i<4;i++){int dx=x+dir[i][0];int dy=y+dir[i][1];if(!use[dx][dy]&&dx>=0&&dx<=n&&dy>=0&&dy<=m&&map[dx][dy]!='#'){if(map[dx][dy]!='.') //如果這個點為數(shù)字寶藏{money=money+map[dx][dy]-'0'; //走這一個點use[x][y]=0; //數(shù)字點可以重復走time++; //時間++DFS(dx,dy,time,money); //下一步time--; //回溯 不走這個點use[x][y]=1;money=money-(map[dx][dy]-'0');}else{use[dx][dy]=1; //如果這個只是.就不能重復走，標記走過注意和數(shù)字的處理不同time++; //單純的時間++DFS(dx,dy,time,money); time--; //回溯use[dx][dy]=0;}}}} int main() {int T,dx,dy;scanf("%d",&T);while(T--){memset(use,0,sizeof(use));t=9999999;scanf("%d%d",&n,&m);for(int i=0;i<=n;i++){scanf("%s",map[i]);}scanf("%d",&sum);for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){if(map[i][j]=='*'){dx=i;dy=j;use[i][j]=1;}}}DFS(dx,dy,0,0);if(t==9999999)printf("-1\n");elseprintf("%d\n",t);} return 0; }

BFS寫，注意use標記數(shù)組，保存走到該點獲得該寶藏的最小步數(shù)，

#include<stdio.h> #include<string.h> #include<queue> #define MAXN 105 using namespace std; int dir[4][2]={-1,0,0,-1,1,0,0,1}; char map[105][105]; int n,m,time,sum; int use[105][105][105]; //表示走到該點獲得的寶藏的最小步數(shù) struct node {int x;int y;int money; }; queue<node>que; int BFS() {node now,next;while(!que.empty()){node now=que.front();que.pop();//printf("%d %d %d\n",now.x,now.y,now.money);for(int i=0;i<4;i++){next.x=now.x+dir[i][0];next.y=now.y+dir[i][1];if(next.x>=0&&next.y>=0&&next.x<=n&&next.y<=m&&map[next.x][next.y]!='#'){next.money=now.money+map[next.x][next.y]-'0'; if(next.money==sum)return use[now.x][now.y][now.money]+1;if(next.money>sum) //剪枝continue ;if(use[next.x][next.y][next.money]>use[now.x][now.y][now.money]+1) //入隊{use[next.x][next.y][next.money]=use[now.x][now.y][now.money]+1;que.push(next);}}}}return -1; } int main() {int T;node now1;scanf("%d",&T);while(T--){while(!que.empty()){que.pop();}scanf("%d%d",&n,&m);for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=101;k++)use[i][j][k]=9999;}}for(int i=0;i<=n;i++)scanf("%s",map[i]);scanf("%d",&sum);for(int i=0;i<=n;i++) //預處理 把圖上面的.都變?yōu)?；{for(int j=0;j<=m;j++){if(map[i][j]=='*'){now1.x=i;now1.y=j;now1.money=0;use[i][j][0]=0;map[i][j]='0';que.push(now1);}if(map[i][j]=='.')map[i][j]='0';}}if(sum==0)printf("0\n");elseprintf("%d\n",BFS());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的swust 1646 迷宫与宝藏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。