题目：
这有一个迷宫，有0~8行和0~8列：
1,1,1,1,1,1,1,1,1 1,0,0,1,0,0,1,0,1 1,0,0,1,1,0,0,0,1 1,0,1,0,1,1,0,1,1 1,0,0,0,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,0,0,0,1 1,1,1,1,1,1,1,1,1
0表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）
输入 第一行输入一个整数n（0<n<=100），表示有n组测试数据; 随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。 输出 输出最少走几步。 样例输入 2 3 1 5 7 3 1 6 7 样例输出 12 11 代码1(深搜)： #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int x1,y1,x2,y2,min1=999999;//min1代表最小的步数 int go[4][2]= {{1,0},{-1,0},{0,-1},{0,1}}; int map[9][9]= { 1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,1,0,1, 1,0,0,1,1,0,0,0,1, 1,0,1,0,1,1,0,1,1, 1,0,0,0,0,1,0,0,1, 1,1,0,1,0,1,0,0,1, 1,1,0,1,0,1,0,0,1, 1,1,0,1,0,0,0,0,1, 1,1,1,1,1,1,1,1,1 }; void dfs(int x,int y,int s) { if(x==x2&&y==y2) { min1=min(min1,s); return ; }//搜索结束条件，并且更新Min1 if(s>min1) return ;//剪枝，当步数比这个min1大的时候没有搜索下去的必要了 for(int i=0; i<4; i++) { int xx=x+go[i][0],yy=y+go[i][1];//下一步要到达的地方 if(xx>=0&&xx<9&&yy>=0&&yy<9&&map[xx][yy]==0)//判断是否越界 { map[xx][yy]=1;//先把走过的标记为墙 dfs(xx,yy,s+1);//搜索下一层 map[xx][yy]=0;//还原迷宫 } } } int main() { int t; scanf("%d",&t); while(t--) { min1=999999;//初始化min1 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//输入起始和终点坐标 dfs(x1,y1,0);//从0开始深搜 printf("%d\n",min1); } return 0; } 代码2（广搜）： #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int x1,y1,x2,y2; int go[4][2]= {{1,0},{-1,0},{0,-1},{0,1}};//上下左右四个方向 int map[9][9]= { 1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,1,0,1, 1,0,0,1,1,0,0,0,1, 1,0,1,0,1,1,0,1,1, 1,0,0,0,0,1,0,0,1, 1,1,0,1,0,1,0,0,1, 1,1,0,1,0,1,0,0,1, 1,1,0,1,0,0,0,0,1, 1,1,1,1,1,1,1,1,1 }; struct Node { int x,y,s; }; bool vis[10][10];//走过的标记为1，没走的标记为0 int bfs(int x,int y) { Node now,to;//现在的和将要走的 now.x=x,now.y=y,now.s=0; queue<Node>q; vis[x][y]=1;//把当前的坐标标记 q.push(now); while(!q.empty()) { now=q.front(); if(now.x==x2&&now.y==y2) return now.s;//满足条件，返回步数 q.pop(); for(int i=0;i<4;i++) { int xx=now.x+go[i][0],yy=now.y+go[i][1];//下一步要走的坐标 if(xx>=0&&xx<9&&yy>=0&&yy<9&&map[xx][yy]==0&&vis[xx][yy]==0)//判断是否越界 { vis[xx][yy]=1;//把走过的标记 to.x=xx,to.y=yy,to.s=now.s+1; q.push(to); } } } return -1;//当队列为空，证明从起点到不了终点，返回-1 } int main() { int t; scanf("%d",&t); while(t--) { mem(vis,0);//初始化标记数组 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//输入起始和终点坐标 printf("%d\n",bfs(x1,y1)); } return 0; } PS:深搜和广搜经典题------再贴一个大神的代码，只能说膜拜
#include<stdio.h> int f[9][9][9][9]; int main() { int n,a,b,c,d; f[1][1][1][1]=0; f[1][1][1][2]=1; f[1][1][1][4]=19; f[1][1][1][5]=18; f[1][1][1][7]=18; f[1][1][2][1]=1; f[1][1][2][2]=2; f[1][1][2][5]=17; f[1][1][2][6]=16; f[1][1][2][7]=17; f[1][1][3][1]=2; f[1][1][3][3]=6; f[1][1][3][6]=15; f[1][1][4][1]=3; f[1][1][4][2]=4; f[1][1][4][3]=5; f[1][1][4][4]=6; f[1][1][4][6]=14; f[1][1][4][7]=15; f[1][1][5][2]=5; f[1][1][5][4]=7; f[1][1][5][6]=13; f[1][1][5][7]=14; f[1][1][6][2]=6; f[1][1][6][4]=8; f[1][1][6][6]=12; f[1][1][6][7]=13; f[1][1][7][2]=7; f[1][1][7][4]=9; f[1][1][7][5]=10; f[1][1][7][6]=11; f[1][1][7][7]=12; f[1][2][1][1]=1; f[1][2][1][2]=0; f[1][2][1][4]=20; f[1][2][1][5]=19; f[1][2][1][7]=19; f[1][2][2][1]=2; f[1][2][2][2]=1; f[1][2][2][5]=18; f[1][2][2][6]=17; f[1][2][2][7]=18; f[1][2][3][1]=3; f[1][2][3][3]=7; f[1][2][3][6]=16; f[1][2][4][1]=4; f[1][2][4][2]=5; f[1][2][4][3]=6; f[1][2][4][4]=7; f[1][2][4][6]=15; f[1][2][4][7]=16; f[1][2][5][2]=6; f[1][2][5][4]=8; f[1][2][5][6]=14; f[1][2][5][7]=15; f[1][2][6][2]=7; f[1][2][6][4]=9; f[1][2][6][6]=13; f[1][2][6][7]=14; f[1][2][7][2]=8; f[1][2][7][4]=10; f[1][2][7][5]=11; f[1][2][7][6]=12; f[1][2][7][7]=13; f[1][4][1][1]=19; f[1][4][1][2]=20; f[1][4][1][4]=0; f[1][4][1][5]=1; f[1][4][1][7]=5; f[1][4][2][1]=18; f[1][4][2][2]=19; f[1][4][2][5]=2; f[1][4][2][6]=3; f[1][4][2][7]=4; f[1][4][3][1]=17; f[1][4][3][3]=15; f[1][4][3][6]=4; f[1][4][4][1]=16; f[1][4][4][2]=15; f[1][4][4][3]=14; f[1][4][4][4]=13; f[1][4][4][6]=5; f[1][4][4][7]=6; f[1][4][5][2]=16; f[1][4][5][4]=12; f[1][4][5][6]=6; f[1][4][5][7]=7; f[1][4][6][2]=17; f[1][4][6][4]=11; f[1][4][6][6]=7; f[1][4][6][7]=8; f[1][4][7][2]=18; f[1][4][7][4]=10; f[1][4][7][5]=9; f[1][4][7][6]=8; f[1][4][7][7]=9; f[1][5][1][1]=18; f[1][5][1][2]=19; f[1][5][1][4]=1; f[1][5][1][5]=0; f[1][5][1][7]=4; f[1][5][2][1]=17; f[1][5][2][2]=18; f[1][5][2][5]=1; f[1][5][2][6]=2; f[1][5][2][7]=3; f[1][5][3][1]=16; f[1][5][3][3]=14; f[1][5][3][6]=3; f[1][5][4][1]=15; f[1][5][4][2]=14; f[1][5][4][3]=13; f[1][5][4][4]=12; f[1][5][4][6]=4; f[1][5][4][7]=5; f[1][5][5][2]=15; f[1][5][5][4]=11; f[1][5][5][6]=5; f[1][5][5][7]=6; f[1][5][6][2]=16; f[1][5][6][4]=10; f[1][5][6][6]=6; f[1][5][6][7]=7; f[1][5][7][2]=17; f[1][5][7][4]=9; f[1][5][7][5]=8; f[1][5][7][6]=7; f[1][5][7][7]=8; f[1][7][1][1]=18; f[1][7][1][2]=19; f[1][7][1][4]=5; f[1][7][1][5]=4; f[1][7][1][7]=0; f[1][7][2][1]=17; f[1][7][2][2]=18; f[1][7][2][5]=3; f[1][7][2][6]=2; f[1][7][2][7]=1; f[1][7][3][1]=16; f[1][7][3][3]=14; f[1][7][3][6]=3; f[1][7][4][1]=15; f[1][7][4][2]=14; f[1][7][4][3]=13; f[1][7][4][4]=12; f[1][7][4][6]=4; f[1][7][4][7]=5; f[1][7][5][2]=15; f[1][7][5][4]=11; f[1][7][5][6]=5; f[1][7][5][7]=6; f[1][7][6][2]=16; f[1][7][6][4]=10; f[1][7][6][6]=6; f[1][7][6][7]=7; f[1][7][7][2]=17; f[1][7][7][4]=9; f[1][7][7][5]=8; f[1][7][7][6]=7; f[1][7][7][7]=8; f[2][1][1][1]=1; f[2][1][1][2]=2; f[2][1][1][4]=18; f[2][1][1][5]=17; f[2][1][1][7]=17; f[2][1][2][1]=0; f[2][1][2][2]=1; f[2][1][2][5]=16; f[2][1][2][6]=15; f[2][1][2][7]=16; f[2][1][3][1]=1; f[2][1][3][3]=5; f[2][1][3][6]=14; f[2][1][4][1]=2; f[2][1][4][2]=3; f[2][1][4][3]=4; f[2][1][4][4]=5; f[2][1][4][6]=13; f[2][1][4][7]=14; f[2][1][5][2]=4; f[2][1][5][4]=6; f[2][1][5][6]=12; f[2][1][5][7]=13; f[2][1][6][2]=5; f[2][1][6][4]=7; f[2][1][6][6]=11; f[2][1][6][7]=12; f[2][1][7][2]=6; f[2][1][7][4]=8; f[2][1][7][5]=9; f[2][1][7][6]=10; f[2][1][7][7]=11; f[2][2][1][1]=2; f[2][2][1][2]=1; f[2][2][1][4]=19; f[2][2][1][5]=18; f[2][2][1][7]=18; f[2][2][2][1]=1; f[2][2][2][2]=0; f[2][2][2][5]=17; f[2][2][2][6]=16; f[2][2][2][7]=17; f[2][2][3][1]=2; f[2][2][3][3]=6; f[2][2][3][6]=15; f[2][2][4][1]=3; f[2][2][4][2]=4; f[2][2][4][3]=5; f[2][2][4][4]=6; f[2][2][4][6]=14; f[2][2][4][7]=15; f[2][2][5][2]=5; f[2][2][5][4]=7; f[2][2][5][6]=13; f[2][2][5][7]=14; f[2][2][6][2]=6; f[2][2][6][4]=8; f[2][2][6][6]=12; f[2][2][6][7]=13; f[2][2][7][2]=7; f[2][2][7][4]=9; f[2][2][7][5]=10; f[2][2][7][6]=11; f[2][2][7][7]=12; f[2][5][1][1]=17; f[2][5][1][2]=18; f[2][5][1][4]=2; f[2][5][1][5]=1; f[2][5][1][7]=3; f[2][5][2][1]=16; f[2][5][2][2]=17; f[2][5][2][5]=0; f[2][5][2][6]=1; f[2][5][2][7]=2; f[2][5][3][1]=15; f[2][5][3][3]=13; f[2][5][3][6]=2; f[2][5][4][1]=14; f[2][5][4][2]=13; f[2][5][4][3]=12; f[2][5][4][4]=11; f[2][5][4][6]=3; f[2][5][4][7]=4; f[2][5][5][2]=14; f[2][5][5][4]=10; f[2][5][5][6]=4; f[2][5][5][7]=5; f[2][5][6][2]=15; f[2][5][6][4]=9; f[2][5][6][6]=5; f[2][5][6][7]=6; f[2][5][7][2]=16; f[2][5][7][4]=8; f[2][5][7][5]=7; f[2][5][7][6]=6; f[2][5][7][7]=7; f[2][6][1][1]=16; f[2][6][1][2]=17; f[2][6][1][4]=3; f[2][6][1][5]=2; f[2][6][1][7]=2; f[2][6][2][1]=15; f[2][6][2][2]=16; f[2][6][2][5]=1; f[2][6][2][6]=0; f[2][6][2][7]=1; f[2][6][3][1]=14; f[2][6][3][3]=12; f[2][6][3][6]=1; f[2][6][4][1]=13; f[2][6][4][2]=12; f[2][6][4][3]=11; f[2][6][4][4]=10; f[2][6][4][6]=2; f[2][6][4][7]=3; f[2][6][5][2]=13; f[2][6][5][4]=9; f[2][6][5][6]=3; f[2][6][5][7]=4; f[2][6][6][2]=14; f[2][6][6][4]=8; f[2][6][6][6]=4; f[2][6][6][7]=5; f[2][6][7][2]=15; f[2][6][7][4]=7; f[2][6][7][5]=6; f[2][6][7][6]=5; f[2][6][7][7]=6; f[2][7][1][1]=17; f[2][7][1][2]=18; f[2][7][1][4]=4; f[2][7][1][5]=3; f[2][7][1][7]=1; f[2][7][2][1]=16; f[2][7][2][2]=17; f[2][7][2][5]=2; f[2][7][2][6]=1; f[2][7][2][7]=0; f[2][7][3][1]=15; f[2][7][3][3]=13; f[2][7][3][6]=2; f[2][7][4][1]=14; f[2][7][4][2]=13; f[2][7][4][3]=12; f[2][7][4][4]=11; f[2][7][4][6]=3; f[2][7][4][7]=4; f[2][7][5][2]=14; f[2][7][5][4]=10; f[2][7][5][6]=4; f[2][7][5][7]=5; f[2][7][6][2]=15; f[2][7][6][4]=9; f[2][7][6][6]=5; f[2][7][6][7]=6; f[2][7][7][2]=16; f[2][7][7][4]=8; f[2][7][7][5]=7; f[2][7][7][6]=6; f[2][7][7][7]=7; f[3][1][1][1]=2; f[3][1][1][2]=3; f[3][1][1][4]=17; f[3][1][1][5]=16; f[3][1][1][7]=16; f[3][1][2][1]=1; f[3][1][2][2]=2; f[3][1][2][5]=15; f[3][1][2][6]=14; f[3][1][2][7]=15; f[3][1][3][1]=0; f[3][1][3][3]=4; f[3][1][3][6]=13; f[3][1][4][1]=1; f[3][1][4][2]=2; f[3][1][4][3]=3; f[3][1][4][4]=4; f[3][1][4][6]=12; f[3][1][4][7]=13; f[3][1][5][2]=3; f[3][1][5][4]=5; f[3][1][5][6]=11; f[3][1][5][7]=12; f[3][1][6][2]=4; f[3][1][6][4]=6; f[3][1][6][6]=10; f[3][1][6][7]=11; f[3][1][7][2]=5; f[3][1][7][4]=7; f[3][1][7][5]=8; f[3][1][7][6]=9; f[3][1][7][7]=10; f[3][3][1][1]=6; f[3][3][1][2]=7; f[3][3][1][4]=15; f[3][3][1][5]=14; f[3][3][1][7]=14; f[3][3][2][1]=5; f[3][3][2][2]=6; f[3][3][2][5]=13; f[3][3][2][6]=12; f[3][3][2][7]=13; f[3][3][3][1]=4; f[3][3][3][3]=0; f[3][3][3][6]=11; f[3][3][4][1]=3; f[3][3][4][2]=2; f[3][3][4][3]=1; f[3][3][4][4]=2; f[3][3][4][6]=10; f[3][3][4][7]=11; f[3][3][5][2]=3; f[3][3][5][4]=3; f[3][3][5][6]=9; f[3][3][5][7]=10; f[3][3][6][2]=4; f[3][3][6][4]=4; f[3][3][6][6]=8; f[3][3][6][7]=9; f[3][3][7][2]=5; f[3][3][7][4]=5; f[3][3][7][5]=6; f[3][3][7][6]=7; f[3][3][7][7]=8; f[3][6][1][1]=15; f[3][6][1][2]=16; f[3][6][1][4]=4; f[3][6][1][5]=3; f[3][6][1][7]=3; f[3][6][2][1]=14; f[3][6][2][2]=15; f[3][6][2][5]=2; f[3][6][2][6]=1; f[3][6][2][7]=2; f[3][6][3][1]=13; f[3][6][3][3]=11; f[3][6][3][6]=0; f[3][6][4][1]=12; f[3][6][4][2]=11; f[3][6][4][3]=10; f[3][6][4][4]=9; f[3][6][4][6]=1; f[3][6][4][7]=2; f[3][6][5][2]=12; f[3][6][5][4]=8; f[3][6][5][6]=2; f[3][6][5][7]=3; f[3][6][6][2]=13; f[3][6][6][4]=7; f[3][6][6][6]=3; f[3][6][6][7]=4; f[3][6][7][2]=14; f[3][6][7][4]=6; f[3][6][7][5]=5; f[3][6][7][6]=4; f[3][6][7][7]=5; f[4][1][1][1]=3; f[4][1][1][2]=4; f[4][1][1][4]=16; f[4][1][1][5]=15; f[4][1][1][7]=15; f[4][1][2][1]=2; f[4][1][2][2]=3; f[4][1][2][5]=14; f[4][1][2][6]=13; f[4][1][2][7]=14; f[4][1][3][1]=1; f[4][1][3][3]=3; f[4][1][3][6]=12; f[4][1][4][1]=0; f[4][1][4][2]=1; f[4][1][4][3]=2; f[4][1][4][4]=3; f[4][1][4][6]=11; f[4][1][4][7]=12; f[4][1][5][2]=2; f[4][1][5][4]=4; f[4][1][5][6]=10; f[4][1][5][7]=11; f[4][1][6][2]=3; f[4][1][6][4]=5; f[4][1][6][6]=9; f[4][1][6][7]=10; f[4][1][7][2]=4; f[4][1][7][4]=6; f[4][1][7][5]=7; f[4][1][7][6]=8; f[4][1][7][7]=9; f[4][2][1][1]=4; f[4][2][1][2]=5; f[4][2][1][4]=15; f[4][2][1][5]=14; f[4][2][1][7]=14; f[4][2][2][1]=3; f[4][2][2][2]=4; f[4][2][2][5]=13; f[4][2][2][6]=12; f[4][2][2][7]=13; f[4][2][3][1]=2; f[4][2][3][3]=2; f[4][2][3][6]=11; f[4][2][4][1]=1; f[4][2][4][2]=0; f[4][2][4][3]=1; f[4][2][4][4]=2; f[4][2][4][6]=10; f[4][2][4][7]=11; f[4][2][5][2]=1; f[4][2][5][4]=3; f[4][2][5][6]=9; f[4][2][5][7]=10; f[4][2][6][2]=2; f[4][2][6][4]=4; f[4][2][6][6]=8; f[4][2][6][7]=9; f[4][2][7][2]=3; f[4][2][7][4]=5; f[4][2][7][5]=6; f[4][2][7][6]=7; f[4][2][7][7]=8; f[4][3][1][1]=5; f[4][3][1][2]=6; f[4][3][1][4]=14; f[4][3][1][5]=13; f[4][3][1][7]=13; f[4][3][2][1]=4; f[4][3][2][2]=5; f[4][3][2][5]=12; f[4][3][2][6]=11; f[4][3][2][7]=12; f[4][3][3][1]=3; f[4][3][3][3]=1; f[4][3][3][6]=10; f[4][3][4][1]=2; f[4][3][4][2]=1; f[4][3][4][3]=0; f[4][3][4][4]=1; f[4][3][4][6]=9; f[4][3][4][7]=10; f[4][3][5][2]=2; f[4][3][5][4]=2; f[4][3][5][6]=8; f[4][3][5][7]=9; f[4][3][6][2]=3; f[4][3][6][4]=3; f[4][3][6][6]=7; f[4][3][6][7]=8; f[4][3][7][2]=4; f[4][3][7][4]=4; f[4][3][7][5]=5; f[4][3][7][6]=6; f[4][3][7][7]=7; f[4][4][1][1]=6; f[4][4][1][2]=7; f[4][4][1][4]=13; f[4][4][1][5]=12; f[4][4][1][7]=12; f[4][4][2][1]=5; f[4][4][2][2]=6; f[4][4][2][5]=11; f[4][4][2][6]=10; f[4][4][2][7]=11; f[4][4][3][1]=4; f[4][4][3][3]=2; f[4][4][3][6]=9; f[4][4][4][1]=3; f[4][4][4][2]=2; f[4][4][4][3]=1; f[4][4][4][4]=0; f[4][4][4][6]=8; f[4][4][4][7]=9; f[4][4][5][2]=3; f[4][4][5][4]=1; f[4][4][5][6]=7; f[4][4][5][7]=8; f[4][4][6][2]=4; f[4][4][6][4]=2; f[4][4][6][6]=6; f[4][4][6][7]=7; f[4][4][7][2]=5; f[4][4][7][4]=3; f[4][4][7][5]=4; f[4][4][7][6]=5; f[4][4][7][7]=6; f[4][6][1][1]=14; f[4][6][1][2]=15; f[4][6][1][4]=5; f[4][6][1][5]=4; f[4][6][1][7]=4; f[4][6][2][1]=13; f[4][6][2][2]=14; f[4][6][2][5]=3; f[4][6][2][6]=2; f[4][6][2][7]=3; f[4][6][3][1]=12; f[4][6][3][3]=10; f[4][6][3][6]=1; f[4][6][4][1]=11; f[4][6][4][2]=10; f[4][6][4][3]=9; f[4][6][4][4]=8; f[4][6][4][6]=0; f[4][6][4][7]=1; f[4][6][5][2]=11; f[4][6][5][4]=7; f[4][6][5][6]=1; f[4][6][5][7]=2; f[4][6][6][2]=12; f[4][6][6][4]=6; f[4][6][6][6]=2; f[4][6][6][7]=3; f[4][6][7][2]=13; f[4][6][7][4]=5; f[4][6][7][5]=4; f[4][6][7][6]=3; f[4][6][7][7]=4; f[4][7][1][1]=15; f[4][7][1][2]=16; f[4][7][1][4]=6; f[4][7][1][5]=5; f[4][7][1][7]=5; f[4][7][2][1]=14; f[4][7][2][2]=15; f[4][7][2][5]=4; f[4][7][2][6]=3; f[4][7][2][7]=4; f[4][7][3][1]=13; f[4][7][3][3]=11; f[4][7][3][6]=2; f[4][7][4][1]=12; f[4][7][4][2]=11; f[4][7][4][3]=10; f[4][7][4][4]=9; f[4][7][4][6]=1; f[4][7][4][7]=0; f[4][7][5][2]=12; f[4][7][5][4]=8; f[4][7][5][6]=2; f[4][7][5][7]=1; f[4][7][6][2]=13; f[4][7][6][4]=7; f[4][7][6][6]=3; f[4][7][6][7]=2; f[4][7][7][2]=14; f[4][7][7][4]=6; f[4][7][7][5]=5; f[4][7][7][6]=4; f[4][7][7][7]=3; f[5][2][1][1]=5; f[5][2][1][2]=6; f[5][2][1][4]=16; f[5][2][1][5]=15; f[5][2][1][7]=15; f[5][2][2][1]=4; f[5][2][2][2]=5; f[5][2][2][5]=14; f[5][2][2][6]=13; f[5][2][2][7]=14; f[5][2][3][1]=3; f[5][2][3][3]=3; f[5][2][3][6]=12; f[5][2][4][1]=2; f[5][2][4][2]=1; f[5][2][4][3]=2; f[5][2][4][4]=3; f[5][2][4][6]=11; f[5][2][4][7]=12; f[5][2][5][2]=0; f[5][2][5][4]=4; f[5][2][5][6]=10; f[5][2][5][7]=11; f[5][2][6][2]=1; f[5][2][6][4]=5; f[5][2][6][6]=9; f[5][2][6][7]=10; f[5][2][7][2]=2; f[5][2][7][4]=6; f[5][2][7][5]=7; f[5][2][7][6]=8; f[5][2][7][7]=9; f[5][4][1][1]=7; f[5][4][1][2]=8; f[5][4][1][4]=12; f[5][4][1][5]=11; f[5][4][1][7]=11; f[5][4][2][1]=6; f[5][4][2][2]=7; f[5][4][2][5]=10; f[5][4][2][6]=9; f[5][4][2][7]=10; f[5][4][3][1]=5; f[5][4][3][3]=3; f[5][4][3][6]=8; f[5][4][4][1]=4; f[5][4][4][2]=3; f[5][4][4][3]=2; f[5][4][4][4]=1; f[5][4][4][6]=7; f[5][4][4][7]=8; f[5][4][5][2]=4; f[5][4][5][4]=0; f[5][4][5][6]=6; f[5][4][5][7]=7; f[5][4][6][2]=5; f[5][4][6][4]=1; f[5][4][6][6]=5; f[5][4][6][7]=6; f[5][4][7][2]=6; f[5][4][7][4]=2; f[5][4][7][5]=3; f[5][4][7][6]=4; f[5][4][7][7]=5; f[5][6][1][1]=13; f[5][6][1][2]=14; f[5][6][1][4]=6; f[5][6][1][5]=5; f[5][6][1][7]=5; f[5][6][2][1]=12; f[5][6][2][2]=13; f[5][6][2][5]=4; f[5][6][2][6]=3; f[5][6][2][7]=4; f[5][6][3][1]=11; f[5][6][3][3]=9; f[5][6][3][6]=2; f[5][6][4][1]=10; f[5][6][4][2]=9; f[5][6][4][3]=8; f[5][6][4][4]=7; f[5][6][4][6]=1; f[5][6][4][7]=2; f[5][6][5][2]=10; f[5][6][5][4]=6; f[5][6][5][6]=0; f[5][6][5][7]=1; f[5][6][6][2]=11; f[5][6][6][4]=5; f[5][6][6][6]=1; f[5][6][6][7]=2; f[5][6][7][2]=12; f[5][6][7][4]=4; f[5][6][7][5]=3; f[5][6][7][6]=2; f[5][6][7][7]=3; f[5][7][1][1]=14; f[5][7][1][2]=15; f[5][7][1][4]=7; f[5][7][1][5]=6; f[5][7][1][7]=6; f[5][7][2][1]=13; f[5][7][2][2]=14; f[5][7][2][5]=5; f[5][7][2][6]=4; f[5][7][2][7]=5; f[5][7][3][1]=12; f[5][7][3][3]=10; f[5][7][3][6]=3; f[5][7][4][1]=11; f[5][7][4][2]=10; f[5][7][4][3]=9; f[5][7][4][4]=8; f[5][7][4][6]=2; f[5][7][4][7]=1; f[5][7][5][2]=11; f[5][7][5][4]=7; f[5][7][5][6]=1; f[5][7][5][7]=0; f[5][7][6][2]=12; f[5][7][6][4]=6; f[5][7][6][6]=2; f[5][7][6][7]=1; f[5][7][7][2]=13; f[5][7][7][4]=5; f[5][7][7][5]=4; f[5][7][7][6]=3; f[5][7][7][7]=2; f[6][2][1][1]=6; f[6][2][1][2]=7; f[6][2][1][4]=17; f[6][2][1][5]=16; f[6][2][1][7]=16; f[6][2][2][1]=5; f[6][2][2][2]=6; f[6][2][2][5]=15; f[6][2][2][6]=14; f[6][2][2][7]=15; f[6][2][3][1]=4; f[6][2][3][3]=4; f[6][2][3][6]=13; f[6][2][4][1]=3; f[6][2][4][2]=2; f[6][2][4][3]=3; f[6][2][4][4]=4; f[6][2][4][6]=12; f[6][2][4][7]=13; f[6][2][5][2]=1; f[6][2][5][4]=5; f[6][2][5][6]=11; f[6][2][5][7]=12; f[6][2][6][2]=0; f[6][2][6][4]=6; f[6][2][6][6]=10; f[6][2][6][7]=11; f[6][2][7][2]=1; f[6][2][7][4]=7; f[6][2][7][5]=8; f[6][2][7][6]=9; f[6][2][7][7]=10; f[6][4][1][1]=8; f[6][4][1][2]=9; f[6][4][1][4]=11; f[6][4][1][5]=10; f[6][4][1][7]=10; f[6][4][2][1]=7; f[6][4][2][2]=8; f[6][4][2][5]=9; f[6][4][2][6]=8; f[6][4][2][7]=9; f[6][4][3][1]=6; f[6][4][3][3]=4; f[6][4][3][6]=7; f[6][4][4][1]=5; f[6][4][4][2]=4; f[6][4][4][3]=3; f[6][4][4][4]=2; f[6][4][4][6]=6; f[6][4][4][7]=7; f[6][4][5][2]=5; f[6][4][5][4]=1; f[6][4][5][6]=5; f[6][4][5][7]=6; f[6][4][6][2]=6; f[6][4][6][4]=0; f[6][4][6][6]=4; f[6][4][6][7]=5; f[6][4][7][2]=7; f[6][4][7][4]=1; f[6][4][7][5]=2; f[6][4][7][6]=3; f[6][4][7][7]=4; f[6][6][1][1]=12; f[6][6][1][2]=13; f[6][6][1][4]=7; f[6][6][1][5]=6; f[6][6][1][7]=6; f[6][6][2][1]=11; f[6][6][2][2]=12; f[6][6][2][5]=5; f[6][6][2][6]=4; f[6][6][2][7]=5; f[6][6][3][1]=10; f[6][6][3][3]=8; f[6][6][3][6]=3; f[6][6][4][1]=9; f[6][6][4][2]=8; f[6][6][4][3]=7; f[6][6][4][4]=6; f[6][6][4][6]=2; f[6][6][4][7]=3; f[6][6][5][2]=9; f[6][6][5][4]=5; f[6][6][5][6]=1; f[6][6][5][7]=2; f[6][6][6][2]=10; f[6][6][6][4]=4; f[6][6][6][6]=0; f[6][6][6][7]=1; f[6][6][7][2]=11; f[6][6][7][4]=3; f[6][6][7][5]=2; f[6][6][7][6]=1; f[6][6][7][7]=2; f[6][7][1][1]=13; f[6][7][1][2]=14; f[6][7][1][4]=8; f[6][7][1][5]=7; f[6][7][1][7]=7; f[6][7][2][1]=12; f[6][7][2][2]=13; f[6][7][2][5]=6; f[6][7][2][6]=5; f[6][7][2][7]=6; f[6][7][3][1]=11; f[6][7][3][3]=9; f[6][7][3][6]=4; f[6][7][4][1]=10; f[6][7][4][2]=9; f[6][7][4][3]=8; f[6][7][4][4]=7; f[6][7][4][6]=3; f[6][7][4][7]=2; f[6][7][5][2]=10; f[6][7][5][4]=6; f[6][7][5][6]=2; f[6][7][5][7]=1; f[6][7][6][2]=11; f[6][7][6][4]=5; f[6][7][6][6]=1; f[6][7][6][7]=0; f[6][7][7][2]=12; f[6][7][7][4]=4; f[6][7][7][5]=3; f[6][7][7][6]=2; f[6][7][7][7]=1; f[7][2][1][1]=7; f[7][2][1][2]=8; f[7][2][1][4]=18; f[7][2][1][5]=17; f[7][2][1][7]=17; f[7][2][2][1]=6; f[7][2][2][2]=7; f[7][2][2][5]=16; f[7][2][2][6]=15; f[7][2][2][7]=16; f[7][2][3][1]=5; f[7][2][3][3]=5; f[7][2][3][6]=14; f[7][2][4][1]=4; f[7][2][4][2]=3; f[7][2][4][3]=4; f[7][2][4][4]=5; f[7][2][4][6]=13; f[7][2][4][7]=14; f[7][2][5][2]=2; f[7][2][5][4]=6; f[7][2][5][6]=12; f[7][2][5][7]=13; f[7][2][6][2]=1; f[7][2][6][4]=7; f[7][2][6][6]=11; f[7][2][6][7]=12; f[7][2][7][2]=0; f[7][2][7][4]=8; f[7][2][7][5]=9; f[7][2][7][6]=10; f[7][2][7][7]=11; f[7][4][1][1]=9; f[7][4][1][2]=10; f[7][4][1][4]=10; f[7][4][1][5]=9; f[7][4][1][7]=9; f[7][4][2][1]=8; f[7][4][2][2]=9; f[7][4][2][5]=8; f[7][4][2][6]=7; f[7][4][2][7]=8; f[7][4][3][1]=7; f[7][4][3][3]=5; f[7][4][3][6]=6; f[7][4][4][1]=6; f[7][4][4][2]=5; f[7][4][4][3]=4; f[7][4][4][4]=3; f[7][4][4][6]=5; f[7][4][4][7]=6; f[7][4][5][2]=6; f[7][4][5][4]=2; f[7][4][5][6]=4; f[7][4][5][7]=5; f[7][4][6][2]=7; f[7][4][6][4]=1; f[7][4][6][6]=3; f[7][4][6][7]=4; f[7][4][7][2]=8; f[7][4][7][4]=0; f[7][4][7][5]=1; f[7][4][7][6]=2; f[7][4][7][7]=3; f[7][5][1][1]=10; f[7][5][1][2]=11; f[7][5][1][4]=9; f[7][5][1][5]=8; f[7][5][1][7]=8; f[7][5][2][1]=9; f[7][5][2][2]=10; f[7][5][2][5]=7; f[7][5][2][6]=6; f[7][5][2][7]=7; f[7][5][3][1]=8; f[7][5][3][3]=6; f[7][5][3][6]=5; f[7][5][4][1]=7; f[7][5][4][2]=6; f[7][5][4][3]=5; f[7][5][4][4]=4; f[7][5][4][6]=4; f[7][5][4][7]=5; f[7][5][5][2]=7; f[7][5][5][4]=3; f[7][5][5][6]=3; f[7][5][5][7]=4; f[7][5][6][2]=8; f[7][5][6][4]=2; f[7][5][6][6]=2; f[7][5][6][7]=3; f[7][5][7][2]=9; f[7][5][7][4]=1; f[7][5][7][5]=0; f[7][5][7][6]=1; f[7][5][7][7]=2; f[7][6][1][1]=11; f[7][6][1][2]=12; f[7][6][1][4]=8; f[7][6][1][5]=7; f[7][6][1][7]=7; f[7][6][2][1]=10; f[7][6][2][2]=11; f[7][6][2][5]=6; f[7][6][2][6]=5; f[7][6][2][7]=6; f[7][6][3][1]=9; f[7][6][3][3]=7; f[7][6][3][6]=4; f[7][6][4][1]=8; f[7][6][4][2]=7; f[7][6][4][3]=6; f[7][6][4][4]=5; f[7][6][4][6]=3; f[7][6][4][7]=4; f[7][6][5][2]=8; f[7][6][5][4]=4; f[7][6][5][6]=2; f[7][6][5][7]=3; f[7][6][6][2]=9; f[7][6][6][4]=3; f[7][6][6][6]=1; f[7][6][6][7]=2; f[7][6][7][2]=10; f[7][6][7][4]=2; f[7][6][7][5]=1; f[7][6][7][6]=0; f[7][6][7][7]=1; f[7][7][1][1]=12; f[7][7][1][2]=13; f[7][7][1][4]=9; f[7][7][1][5]=8; f[7][7][1][7]=8; f[7][7][2][1]=11; f[7][7][2][2]=12; f[7][7][2][5]=7; f[7][7][2][6]=6; f[7][7][2][7]=7; f[7][7][3][1]=10; f[7][7][3][3]=8; f[7][7][3][6]=5; f[7][7][4][1]=9; f[7][7][4][2]=8; f[7][7][4][3]=7; f[7][7][4][4]=6; f[7][7][4][6]=4; f[7][7][4][7]=3; f[7][7][5][2]=9; f[7][7][5][4]=5; f[7][7][5][6]=3; f[7][7][5][7]=2; f[7][7][6][2]=10; f[7][7][6][4]=4; f[7][7][6][6]=2; f[7][7][6][7]=1; f[7][7][7][2]=11; f[7][7][7][4]=3; f[7][7][7][5]=2; f[7][7][7][6]=1; f[7][7][7][7]=0; scanf("%d",&n); while(n--) { scanf("%d%d%d%d",&a,&b,&c,&d); printf("%d\n",f[a][b][c][d]); } return 0; }
