问题 C: Knight Moves

时间限制: 1 Sec 内存限制: 128 MB
提交: 13 解决: 7
[提交][状态][讨论版][命题人:add_shengjunjie][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1694&pid=2

题目描述

       佳佳是一名出色的棋手，声称任何人他都可以从一个位置到另一个骑士这么快。你能打败他吗？
问题
       你的任务是写一个程序来计算一个骑士达到从另一点所需要的最少步数。
       对于不熟悉象棋的人，可能的骑士动作如图所示。

输入

输入开始与一个单一的行本身的情况下。
下一步跟踪N个场景。每个场景由三行包含整数。第一行指定棋盘边的长度L（4 < L = < 300）。整个板尺寸L×L的第二和第三行包含整数对{ 0，…，L-1 } * { 0，…，L-1 }指定开始和结束位置的骑士。整数由一个空格隔开。您可以假定这些位置是该方案的棋盘上的有效位置.。

输出

对于输入的每一个场景，你必须计算从起点到终点的最小的骑士移动量.。如果起点和终点相等，距离为零。距离必须写在一行。

样例输入

样例输出

思路：原本这题是普通的BFS就能过的，迷宫不大，但是为了更快的效率，我们用两个队列去做，当队列1弹出的目标如果此时队列2在此处已经被访问过了，就代表找到了最短路径，相反也是一样的道理，总步数则为bushu[xx][yy][1] + bushu[xx][yy][0]。

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000

//int Map[maxn][maxn];

int sx, sy, ex, ey, n;

int fx[8] = { -2,-1,1,2,2,1,-1,-2 };//构建方向

int fy[8] = { 1,2,2,1,-1,-2,-2,-1 };

//int vis[maxn][maxn];

int bushu[maxn][maxn][2];//2个队列的步数记录

struct Map

{

    int x, y;

};

void bfs()

{

    Map start;

    start.x = sx;

    start.y = sy;

    queue<Map>q1;//在起点建队列

    q1.push(start);

    Map end;

    end.x = ex;

    end.y = ey;

    queue<Map>q2;//在终点建队列

    q2.push(end);

    while (!q1.empty() || !q2.empty())

    {

         if (q1.size() >= q2.size())

         {

             Map Node = q2.front();

             q2.pop();

             for (int i = 0; i < 8; i++)

             {

                  int xx = Node.x + fx[i];

                  int yy = Node.y + fy[i];

                  if (xx >= 0 && xx < n&&yy >= 0 && yy < n&&bushu[xx][yy][1] == -1)

                  {

                      bushu[xx][yy][1] = bushu[Node.x][Node.y][1] + 1;//步数的上一步加1

                      if (bushu[xx][yy][0] != -1)

                      {

                           cout << bushu[xx][yy][1] + bushu[xx][yy][0] << endl;//总步数的2个队列的分步数之和

                          return;

                      }

                      Map New;

                      New.x = xx;

                      New.y = yy;

                      q2.push(New);

                  }

             }

         }

         else

         {



             Map Node = q1.front();

             q1.pop();

             for (int i = 0; i < 8; i++)

             {

                  int xx = Node.x + fx[i];

                  int yy = Node.y + fy[i];

                  if (xx >= 0 && xx < n&&yy >= 0 && yy < n&&bushu[xx][yy][0] == -1)

                  {

                      bushu[xx][yy][0] = bushu[Node.x][Node.y][0] + 1;

                      if (bushu[xx][yy][1] != -1)

                      {

                          cout << bushu[xx][yy][1] + bushu[xx][yy][0] << endl;

                          return;

                      }

                      Map New;

                      New.x = xx;

                      New.y = yy;

                      q1.push(New);

                  }

             }

         }

    }

}

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

         memset(bushu, -1, sizeof(bushu));

         cin >> n;

         //memset(vis,0,sizeof(vis));

         cin >> sx >> sy >> ex >> ey;

         bushu[sx][sy][0] = 0;//起点终点步数初始化

         bushu[ex][ey][1] = 0;

         if (sx == ex && sy == ey)cout << 0 << endl;

         else

             bfs();



    }

}