机器人要在一个矩形迷宫里行动（不能原地停留，只能走向上/下/左/右），每移动一格花费1个单位时间。
迷宫有以下几种元素：
【*】 机器人的起点
【#】 墙。机器人不能走过这些格子
【.】 平地。机器人可以在上面自由行走
【0-9】 宝藏。当机器人走到此处会立刻获得该数字相应的宝藏，宝藏不会消失，可以反复获取（但不能停留）
若机器人要恰好获得总和为x的宝藏，它最少需要多少时间？
输入
第一行输入任务数量T, 接下来有T个任务
每块第一行有两个整数, n(0<= n<100), m(0 <=m < 100), 表示迷宫有n+1行和m+1列
接下来n行输入迷宫
最后一行输入你要收集的宝藏的总价值x(0<=x ≤ 100)
输出
对于每个任务，输出最少花费的时间，如果完成不了该任务则输出-1
样例输入
3
2 3
1.#2
#..#
*.#.
3
2 3
2.#2
#..#
*.#.
5
2 3
2.#2
#.3#
*.#.
5
样例输出
8
-1
6
解题思路：用bfs对每个位置的每种可能进行枚举
#include <bits/stdc++.h> using namespace std; char s[105][105]; int vis[105][105][105]; int n,m,k,T,f; int dir[4][2]={0,1,0,-1,1,0,-1,0}; struct node { int x,y,t,v; node(){} node(int x,int y,int v,int t):x(x),y(y),v(v),t(t){} }; queue<node>qu; void bfs(int x,int y) { qu.push(node(x,y,0,0)); vis[x][y][0]=1; while(!qu.empty()){ node temp=qu.front();qu.pop(); int x=temp.x,y=temp.y,t=temp.t,v=temp.v; if(v==k){ printf("%d\n",t); f=1; return; } for(int i=0;i<4;i++){ int xx=x+dir[i][0],yy=y+dir[i][1],tt=t+1,vv=v; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&s[xx][yy]!=\'#\'){ if(s[xx][yy]>=\'1\'&&s[xx][yy]<=\'9\'){ vv=vv+s[xx][yy]-\'0\'; } if(vis[xx][yy][vv]==0&&vv<=k){ vis[xx][yy][vv]=1; qu.push(node(xx,yy,vv,tt)); } } } } } int main() { scanf("%d",&T); while(T--){ f=0; scanf("%d%d",&n,&m); n++,m++; while(!qu.empty()) qu.pop(); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); scanf("%d",&k); for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int a=0;a<=k;a++) vis[i][j][a]=0; } } int x,y; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]==\'*\') x=i,y=j; } } bfs(x,y); if(f==0) printf("-1\n"); } return 0; }