题目链接：

 

#include 
     
      #include 
      
       #include 
       
        #define INF 0x3f3f3f3fusing namespace std;int MAPN[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},};int color[9][9];int mov[4][2]= {
   {
   1,0},{-1,0},{
   0,1},{
   0,-1}};int dfs(int sx,int sy,int x,int y){    int step=INF;    if(sx==x&&sy==y)        return 0;    else    {        for(int k=0; k<4; k++)        {            int tx=sx+mov[k][0];            int ty=sy+mov[k][1];            if(tx>=0&&tx<=8&&ty>=0&&ty<=8)            {                if(!color[tx][ty]&&!MAPN[tx][ty])                {                    color[tx][ty]=1;                    step=min(step,dfs(tx,ty,x,y)+1);                    color[tx][ty]=0;                }            }        }        return step;    }}int main(){    int sx,sy,x,y;///起始位置，目标位置。    int t;    scanf("%d",&t);    while(t--)    {        memset(color,0,sizeof(color));        scanf("%d%d%d%d",&sx,&sy,&x,&y);        printf("%d\n",dfs(sx,sy,x,y));    }    return 0;}