问题链接：。

题意简述：输入测试用例数量，输入棋盘大小，输入国际象棋棋盘中的两个点，求马从一个点跳到另一个点的最少步数。

问题分析：典型的BFS问题。在BFS搜索过程中，马跳过的点就不必再跳了，因为这次再跳下去不可能比上次步数少。

程序中，使用了一个队列来存放中间节点，但是每次用完需要清空。

AC的C++语言程序如下：

/* POJ1915 Knight Moves */#include 
    
     #include 
     
      #include 
      
       using namespace std;#define MAXN 300#define DIRECTSIZE 8struct direct {    int drow;    int dcol;} direct[DIRECTSIZE] =    {
   {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};char grid[MAXN][MAXN];int n, l;int startcol, startrow, endcol, endrow;int ans;struct node {    int row;    int col;    int level;};void bfs(){    queue
       
         q;    memset(grid, 0, sizeof(grid));    grid[startrow][startcol] = 1;    ans = 0;    node start;    start.row = startrow;    start.col = startcol;    start.level = 0;    q.push(start);    while(!q.empty()) {        node front = q.front();        q.pop();        if(front.row == endrow && front.col == endcol) {            ans = front.level;            break;        }        for(int i=0; i