1 /* 2 转自http://blog.csdn.net/custqi/article/details/6455425 3 感觉对双向广搜写得挺清楚的 4 */ 5 #include
     
       6 #include
      
        7 #include
       
         8 using namespace std; 9 const int maxn = 301;10 int n;11 int used[maxn][maxn];12 int g[maxn][maxn];13 int d[8][2] = { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } };14 15 struct Point16 {17     int x, y;18 }st, ed;19 int Check(int x, int y)20 {21     return (x >= 0 && x
        
         = 0 && y
         
          Q;27     Point curNode, nextNode;28     memset(used, 0, sizeof(used));29     //放入起始结点30     g[st.x][st.y] = 0;31     used[st.x][st.y] = 1;//由起始结点方向扩展的结点记录值为 1    32     Q.push(st);33     //放入终止结点34     g[ed.x][ed.y] = 0;35     used[ed.x][ed.y] = 2;//由终止结点方向扩展的结点记录值为 2    36     Q.push(ed);37     //同时放入起始结点和终止结点 进行双向广搜38     while (!Q.empty())39     {40         curNode = Q.front();41         Q.pop();42         sx = curNode.x;43         sy = curNode.y;44         for (int i = 0; i<8; i++)45         {46             tx = sx + d[i][0];47             ty = sy + d[i][1];48             if (!Check(tx, ty)) continue;49             if (used[tx][ty] == 0)    //如果used[tx][ty]未访问过            50             {51                 g[tx][ty] = g[sx][sy] + 1; //更新在tx ty的值                52                 nextNode.x = tx;53                 nextNode.y = ty;54                 used[tx][ty] = used[sx][sy]; //                 55                 Q.push(nextNode);56             }57             else if (used[sx][sy] != used[tx][ty])    //起始方向与终止方向同时进行后，此时的结点为俩个方向相遇的点，得到结果        58             {59                 return g[sx][sy] + g[tx][ty] + 1;60             }61         }62     }63     return 0;64 }65 int main()66 {67     int TestCases;68     scanf("%d", &TestCases);69     while (TestCases--)70     {71         scanf("%d%d%d%d%d", &n, &st.x, &st.y, &ed.x, &ed.y);72         printf("%d/n", solve());73     }74     return 0;75 }