/* BFS：重复访问类 关键：对每个点的访问与否取决于到达该点的条件的优劣 （本题关键在于访问该点是能量的多少，比原先多的即可走） */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include<queue> const int INF = 999999; struct node { int x,y,dead; int step; }; queue<node> q; int n,m,time; int mp[10][10]; int vis[10][10]; int xx[4]={1,-1,0,0}; int yy[4]={0,0,1,-1}; int bfs(int x,int y) { node from,rear; from.x=x,from.y=y; from.dead=6; from.step=0; vis[x][y]=6; q.push (from); while(!q.empty ()) { from=q.front (); q.pop (); for(int i=0;i<4;i++) { int dx=from.x+xx[i]; int dy=from.y+yy[i]; if(dx>=0&&dx<n&&dy>=0&&dy<m&&mp[dx][dy]!=0) { rear.x=dx; rear.y=dy; rear.step=from.step+1; rear.dead=from.dead-1; if(rear.dead==0) continue; if(mp[dx][dy]==4) { rear.dead=6; } if(mp[dx][dy]==3) return rear.step; if(rear.dead>vis[dx][dy]) { vis[dx][dy]=rear.dead; q.push (rear); } } } } return -1; } int main() { int t,i,j,x,y; scanf("%d",&t); while(t--) { memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); while(!q.empty ()) q.pop (); scanf("%d%d",&n,&m); for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%d",&mp[i][j]); if(mp[i][j]==2) x=i,y=j; } } printf("%d ",bfs(x,y)); } return 0; } /* 0---墙 1---路 2---开始 3---出口 4---补给点 */