首页 > 代码库 > 棋盘上的距离[POJ-1657]

棋盘上的距离[POJ-1657]

POJ Monthly 2004.5.15 Liu Rujia@POJ

时间限制 1000ms 内存限制 10MB

这道题应该分开考虑。虽然全部用BFS也是可以的,但是显然对于皇后和车是多余的了。

对于皇后和车来说,必然能到,而且最多只需要两步就能到。因此只需要判断是不是在其一步能到的范围,如果不是,则输出2。判断车的范围很简单,只要看横坐标或者纵坐标是不是相等就行了。而判断王后,除了判断垂直和水平能不能到,还要判断斜向能不能到。可以把棋盘看作一个坐标系,每一个位置当作一个整数点,那么斜向的直线可以用点斜方程给出。设王后的坐标为$(x_0,y_0)$,那么王后可达点在直线$f(x,y):y-y_0=±(x-x_0)$上。这时候假设目标点为$(x_1,y_1)$,只需要判断$(x_1,y_1)$能否满足曲线$f(x,y)$即可。在具体的语言实现中,可以将其化为显函数,代入$x_1$后判断是否与$y_1$相等。

王和象就可以用BFS,从起点开始逐渐往外拓展,直到找到目标点为止。直接用BFS来求是没有任何问题的,因为棋盘只有8X8,对于复杂度为$O(VE)$的BFS还是很小的。对于王的周围的点来说,其实很简单,只需要罗列周围八个点即可,而象则略微复杂一些。需要罗列出所有的可达点并将其入队。我这里罗列所有点,依然使用了上面的平面方程思想,以$x$为自变量,在条件范围内根据方程列出对应的$y$,从而找到所有可行的点。根据BFS性质,只要第一次找到这个点,就将其染色并设置当前的层次(以源结点为根的有向树的层次),所以必然是最少的步数。BFS结束时,如果没有经过目标点,说明无法到达。只有象可能出现无法到达的点。实际上,根据象走位的特殊性,可以将格子分为两种颜色,相邻格子的颜色不同,如果目标点跟起始点颜色相同,那么可达,且最多需要两步;反之则不可达。最后附上我的C++实现:

 

 1 #include<cstdio>
 2 #include<map>
 3 #include<cstring>
 4 #include<queue>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define KING 0
 8 #define QUEEN 1
 9 #define CAR 2
10 #define ELEPHANT 3
11 int board[8][8];
12 int solve(int x,int y,int dx,int dy,int mode)
13 {
14     if(dx==x&&dy==y) return 0;
15     int i,j;
16     if(mode==CAR)
17     {
18         if(dx==x||dy==y) return 1;
19         else return 2;
20     }
21     else if(mode==QUEEN)
22     {
23         if(dx==x||dy==y) return 1;
24         else
25         {
26             if(dx-x==dy-y||dx-x==-(dy-y)) return 1;
27             else return 2;
28         }
29     }
30     memset(board,-1,sizeof(int)*64);
31     queue<pair<int,int> > qu;
32     board[x][y]=0;
33     qu.push(pair<int,int>(x,y));
34     while(!qu.empty())
35     {
36         x=qu.front().first;
37         y=qu.front().second;
38         if(x==dx&&y==dy) return board[x][y];
39         if(mode==KING)
40         {
41             for(i=x-1;i<=x+1;i++)
42                 for(j=y-1;j<=y+1;j++)
43                 {
44                     if(i==x&&j==y) continue;
45                     if(i>=0&&i<=7&&j>=0&&j<=7&&board[i][j]==-1)
46                     {
47 
48                         board[i][j]=board[x][y]+1;
49                         qu.push(pair<int,int>(i,j));
50                     }
51                 }
52         }
53         else
54         {
55             for(i=0,j=i+y-x;i<8;i++,j=i+y-x)
56             {
57                 if((i==x&&y==j)||j<0||j>=8) continue;
58                 if(board[i][j]==-1)
59                 {
60                     board[i][j]=board[x][y]+1;
61                     qu.push(pair<int,int>(i,j));
62                 }
63             }
64             for(i=0,j=x+y-i;i<8;i++,j=x+y-i)
65             {
66                 if((i==x&&y==j)||j<0||j>=8) continue;
67                 if(board[i][j]==-1)
68                 {
69                     board[i][j]=board[x][y]+1;
70                     qu.push(pair<int,int>(i,j));
71                 }
72             }
73         }
74         qu.pop();
75     }
76     return -1;
77 }
78 int main()
79 {
80     int T;
81     scanf("%d",&T);
82     while(T--)
83     {
84         char start[10],end[10];
85         scanf("%s %s",start,end);
86         printf("%d ",solve(start[1]-1,7-(start[0]-a),end[1]-1,7-(end[0]-a),KING));
87         printf("%d ",solve(start[1]-1,7-(start[0]-a),end[1]-1,7-(end[0]-a),QUEEN));
88         printf("%d ",solve(start[1]-1,7-(start[0]-a),end[1]-1,7-(end[0]-a),CAR));
89         int r=solve(start[1]-1,7-(start[0]-a),end[1]-1,7-(end[0]-a),ELEPHANT);
90         if(r==-1)printf("Inf\n");
91         else printf("%d\n",r);
92     }
93     return 0;
94 }

 

棋盘上的距离[POJ-1657]