首页 > 代码库 > HDU 1372 (搜索方向稍有改变) Knight Moves

HDU 1372 (搜索方向稍有改变) Knight Moves

2024-07-17 22:28:14   222人阅读

其实手写模拟一个队列也挺简单的，尤其是熟练以后。

尼玛，这题欺负我不懂国际象棋，后来百度了下，国际象棋里骑士的走法就是中国象棋里面的马

所以搜索就有八个方向

对了注意初始化标记数组的时候，不要把起点标记为已走过。

因为测试数据里面有一组 f6 f6，此时样例输出的是0

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 struct Point 8 { 9     int x, y;10     int steps;11 }start, end, qu[100];12 13 int vis[8][8];14 int dir[8][2] = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};15 char col1, col2;16 int row1, row2;17 int head, tail;18 19 bool islegal(int x, int y)20 {21     return (x>=0 && x<8 && y>=0 && y<8 && (!vis[x][y]));22 }23 24 void BFS(void)25 {26     head = 0, tail = 1;27     qu[0].x = start.x;28     qu[0].y = start.y;29     qu[0].steps = 0;30     while(head < tail)31     {32         if(qu[head].x == end.x && qu[head].y == end.y)33         {34             printf("To get from %c%d to %c%d takes %d knight moves.\n", col1, row1, col2, row2, qu[head].steps);35             return;36         }37         for(int i = 0; i < 8; ++i)38         {39             int xx = qu[head].x + dir[i][0];40             int yy = qu[head].y + dir[i][1];41             if(islegal(xx, yy))42             {43                 qu[tail].x = xx;44                 qu[tail].y = yy;45                 qu[tail++].steps = qu[head].steps + 1;46                 vis[xx][yy] = 1;47             }48         }49         ++head;50     }51 }52 53 int main(void)54 {55     #ifdef LOCAL56         freopen("1372in.txt", "r", stdin);57     #endif58 59     while(cin >> col1 >> row1 >> col2 >> row2)60     {61         start.x = row1 - 1, start.y = col1 - ‘a‘;62         end.x = row2 - 1, end.y = col2 - ‘a‘;63         memset(vis, 0, sizeof(vis));64         BFS();65     }66     return 0;67 }
代码君

 


联系
我们