意甲冠军：不解释。
策略：如果；
这个问题也可以用深宽搜索搜索中使用。我曾经写过，使用深层搜索。最近的学校范围内的搜索，拿这个问题来试试你的手。
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
using std::queue;
bool vis[20][20];
const int dir[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 pos[2];//pos[0] = x， pos[1] = y
int step;
};
Node st, en;
bool match(Node a, Node b) //推断是不是到达终点
{
return (a.pos[0] == b.pos[0]&&a.pos[1] == b.pos[1]);
}
int bfs()
{
queue<Node> q;
int i, j;
memset(vis, 0, sizeof(vis));
q.push(st);
vis[st.pos[0]][st.pos[1]] = 1;
int ans = 0x3f3f3f3f; //初始化
while(!q.empty()){
Node u = q.front();
if(match(u, en)){ //wa了一次是由于没有推断终点是不是起点
ans = u.step;
break;
}
for(i = 0; i < 4; i ++){
Node v;
v.pos[0] = u.pos[0]+dir[i][0];
v.pos[1] = u.pos[1]+dir[i][1];
v.step = u.step+1;
if(match(v, en)){
if(v.step < ans)
ans = v.step;
}
else if(!vis[v.pos[0]][v.pos[1]]&&!map[v.pos[0]][v.pos[1]]){
q.push(v);
vis[v.pos[0]][v.pos[1]] = 1;
}
}
q.pop();
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t --){
scanf("%d%d%d%d", &st.pos[0], &st.pos[1], &en.pos[0], &en.pos[1]);
st.step = 0;
printf("%d\n", bfs());
}
return 0;
}