package xj;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class KuaGe { static int T,N,M,sx,sy,ex,ey; static int data[][]; static boolean map[][]; static int Dx[]={-1,0,1,0}; static int Dy[]={0,1,0,-1}; static class Node{ int x; int y; int step; } static Node[]queue; static boolean flag; public static void main(String[] args) throws FileNotFoundException { /* Scanner sc=new Scanner(System.in); */ Scanner sc = new Scanner(new File("src/Dage")); T=sc.nextInt(); for (int t = 0; t < T; t++) { N=sc.nextInt(); M=sc.nextInt(); data=new int [N][M]; map=new boolean[N][M]; queue=new Node[N*M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { data[i][j]=sc.nextInt(); if(data[i][j]==2){sx=i;sy=j;} if(data[i][j]==3){ex=i;ey=j;} } } flag=false; for (int i = 1; i <=N; i++) { //记得回溯 for (int j = 0; j < N; j++) { for (int j2 = 0; j2 < M; j2++) { map[j][j2]=false; } } bfs(i); if(flag){System.out.println(i);break;} } } } private static void bfs(int step) { int head=0; int tail=1; Node n1=new Node(); n1.x=sx; n1.y=sy; n1.step=1; queue[head]=n1; map[sx][sy]=true; while(head<tail){ for (int i = 0; i < 4; i++) { if(i==0||i==2){ int nx=queue[head].x; int ny=queue[head].y; for (int j = 1; j <= step; j++) { int dx=nx+j*Dx[i]; int dy=ny+j*Dy[i]; if(dx>=0&&dy>=0&&dx<N&&dy<M){ if(data[dx][dy]!=0&&!map[dx][dy]){ Node n3=new Node(); n3.x=dx; n3.y=dy; n3.step=queue[head].step+1; queue[tail]=n3; map[dx][dy]=true; tail++; if(dx==ex&&dy==ey){flag=true;return;} } } } } if(i==1||i==3){ int nx=queue[head].x; int ny=queue[head].y; int dx=nx+Dx[i]; int dy=ny+Dy[i]; if(dx>=0&&dy>=0&&dx<N&&dy<M){ if(data[dx][dy]!=0&&!map[dx][dy]){ Node n2=new Node(); n2.x=dx; n2.y=dy; n2.step=queue[head].step+1; queue[tail]=n2; map[dx][dy]=true; tail++; if(dx==ex&&dy==ey){flag=true;return;} } } } } head++; } }
}
//input
4 5 5 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 5 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 2 6 7 0 0 0 0 0 0 0 0 0 0 0 3 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 2 1 0 0 0 0 1 1 1 1 1 1 1 5 5 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0
//output
4 1 2 4
