Sicily 1936. Knight Moves

思路：
- 这道题一开始不理解题意…orz…囧，看大神们理解的。
- 题意是说一个8*8的国际象棋，骑士以马的形式走动（“日”字型），指定两个点，输出最小的步骤。
- 可以利用广度搜索解决。
具体代码如下：

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;

int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};    //可以走八个方向
int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

bool visited[100];

int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(visited, false, sizeof(visited));
        int distance[100] = {0};

        string node1, node2;
        cin >> node1 >> node2;

        int X = (node1[0]-'a')*8 + node1[1]-'1';
        int Y = (node2[0]-'a')*8 + node2[1]-'1';

        queue<int> store;
        store.push(X);
        while (!store.empty()) {
            if (store.front() == Y)
                break;

            int x = store.front()/8;
            int y = store.front()%8;

            for (int i = 0; i < 8; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if (nx < 0||nx > 7||ny < 0||ny > 7)
                    continue;
                int temp = nx*8 + ny;
                
                if (!visited[temp]) {
                    store.push(temp);
                    visited[temp] = true;
                    distance[temp] = distance[store.front()] + 1;
                }
            }
            store.pop();
        }
        cout << "To get from " << node1
             << " to " << node2 << " takes "
             << distance[Y] << " knight moves.\n";
    }
    
    return 0;
}

For study!

FEATURED TAGS