BFS

代码：

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <string.h>
  4 
  5 typedef struct node
  6 {
  7     int x;
  8     int y;
  9     int s;
 10 }node;
 11 
 12 int N,M;
 13 int R,C;
 14 int S,K;
 15 int *chess = NULL;
 16 //int *book = NULL;
 17 node *que = NULL;
 18 
 19 int dirction[8][2] ={
 20     {1,2},
 21     {2,1},
 22     {2,-1,},
 23     {1,-2},
 24     {-1,-2},
 25     {-2,-1},
 26     {-2,1},
 27     {-1,2}
 28 };
 29 
 30 int main(void)
 31 {
 32     int tc, T;
 33 
 34     setbuf(stdout, NULL);
 35 
 36     scanf("%d", &T);
 37     for(tc = 0; tc < T; tc++)
 38     {
 39         
 40         /**********************************
 41         *  Implement your algorithm here. *
 42         ***********************************/
 43         scanf("%d%d",&N,&M);
 44 
 45         //chess = (int *)malloc(sizeof(int)*(N+1)*(M+1));
 46         //memset(chess,0,sizeof(chess));
 47 
 48         //int *book = (int *)malloc(sizeof(int)*(N+1)*(M+1));
 49         //memset(book,0,sizeof(book));
 50         int book[101][101]={0};
 51         
 52         que = (node *)malloc(sizeof(node)*N*M+1);
 53         memset(que,0,sizeof(que));
 54 
 55         scanf("%d%d",&R,&C);
 56         scanf("%d%d",&S,&K);
 57 
 58         int head = 1;
 59         int tail = 1;
 60         
 61         que[tail].x = R;
 62         que[tail].y = C;
 63         que[tail].s = 0;
 64         book[R][C]=1;
 65 
 66 
 67         tail++;
 68         
 69         int flag = 0;
 70         int k = 0;
 71         int qx,qy;
 72 
 73         while(head<tail)
 74         {
 75             for(k = 0; k < 8; k++)
 76             {
 77                 qx=    que[head].x+dirction[k][0];    
 78                 qy=    que[head].y+dirction[k][1];
 79 
 80                 if(qx<1 || qy< 1 || qx > M || qy >N)
 81                     continue;
 82 
 83                 if(book[qx][qy] == 0)
 84                 {
 85                     book[qx][qy] = 1;
 86                     que[tail].x = qx;
 87                     que[tail].y = qy;
 88                     que[tail].s = que[head].s+1;
 89                     
 90                     tail++;
 91                 }
 92                 //printf("%d, %d, %d
",que[tail-1].x,que[tail-1].y,que[tail-1].s);
 93                 if(qx== S && qy== K)
 94                 {
 95                     flag = 1;
 96                     break;
 97                 }
 98             }
 99             
100             if(flag == 1)
101             {
102                 break;
103             }
104 
105             head++;
106         }
107         
108         
109         printf("%d
",que[tail-1].s);
110         // Print the answer to standard output(screen).
111         
112     }
113 
114     return 0;//Your program should return 0 on normal termination.
115 }

测试数据：

测试结果：

2

5