#include <iostream> #include <queue> #include <cstring> using namespace std; int map[10][10]; int sx,sy; int step[10][10]; int _time[10][10]; int T,N,M; int dirx[4] = {-1,0,1,0}; int diry[4] = {0,1,0,-1}; typedef struct { int x; int y; }pos; void BFS() { memset(step,0x3fffffff,sizeof(step)); memset(_time,0,sizeof(_time)); pos ft,tp; ft.x = sx; ft.y = sy; step[ft.x][ft.y] = 0; _time[ft.x][ft.y] = 6; queue<pos> q; q.push(ft); while(!q.empty()) { ft = q.front(); q.pop(); if(map[ft.x][ft.y] == 3 && _time[ft.x][ft.y] > 0) { cout<<step[ft.x][ft.y]<<endl; return; } for(int i = 0; i < 4; i++) { tp.x = ft.x + dirx[i]; tp.y = ft.y + diry[i]; if(tp.x < 0 || tp.x > N-1 || tp.y < 0 || tp.y > M-1) continue; if(map[tp.x][tp.y] == 0) continue; if (step[tp.x][tp.y] <= step[ft.x][ft.y] + 1 && _time[tp.x][tp.y] >= _time[ft.x][ft.y] - 1) continue; step[tp.x][tp.y] = step[ft.x][ft.y] + 1; _time[tp.x][tp.y] = _time[ft.x][ft.y] -1; if(_time[tp.x][tp.y] <= 0) continue; if(map[tp.x][tp.y] == 4) _time[tp.x][tp.y] = 6; q.push(tp); } } puts("-1"); } int main() { cin>>T; while(T--) { cin>>N>>M; for(int i = 0; i < N; i++) { for(int j = 0; j < M ; j++) { cin>>map[i][j]; if(map[i][j] == 2) { sx = i; sy = j; } } } BFS(); } return 0; }