UVA 00439 - Knight Moves

解題觀念

BFS

可以參考我的課程簡報：BFS & DFS
和：Greedy & Graph
關於 BFS 的基本觀念可以參考我的這篇文章：Algorithm - BFS

題目敘述

你的朋友正在做關於西洋棋中騎士旅行問題（Traveling Knight Problem）的研究
他希望你幫他解決一個問題：給你 2 個格子的位置 X 及 Y

請你找出騎士從 X 走到 Y 最少需要走幾步

西洋棋騎士走法：
圖片來源

Input

每筆測試資料一列
每列有 2 個西洋棋的座標位置

每個位置座標是由一個英文字母（a-h，代表棋盤的第幾欄）
及一個數字（1-8，代表棋盤的第幾列）組成

// Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Output

對每一列輸入
輸出：To get from xx to yy takes n knight moves.

// Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

解題觀念簡報參考

STL - Queue

BFS

關於 BFS 的基本觀念可以參考我的這篇文章：Algorithm - BFS

Solution Code

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int row;
    int col;
    int step;
};

int stepRow[] = {1, 2, 2, 1, -1, -2, -2, -1};
int stepCol[] = {-2, -1, 1, 2, 2, 1, -1, -2};

int main(){
    string startX, endY;
    while(cin >> startX >> endY){
        bool visited[8+5][8+5];
        memset(visited, false, sizeof(visited));

        queue<Node> q;
        q.push({startX[1] - '1', startX[0] - 'a', 0});
        visited[startX[1] - '1'][startX[0] - 'a'] = true;
        
        // BFS
        while(!q.empty()){
            int nowRow = q.front().row;
            int nowCol = q.front().col;
            int nowStep = q.front().step;
            if(nowRow == endY[1] - '1' && nowCol == endY[0] - 'a'){
                cout << "To get from " << startX << " to " << endY << " takes " << nowStep << " knight moves." << endl;
                break;
            }
            q.pop();

            for(int i = 0; i < 8; ++i){
                int nextRow = nowRow + stepRow[i];
                int nextCol = nowCol + stepCol[i];

                if(visited[nextRow][nextCol] || nextCol < 0 || nextRow < 0 || nextCol >= 8 || nextRow >= 8) continue;
                q.push({nextRow, nextCol, nowStep + 1});
                visited[nextRow][nextCol] = true;
            }
        }
    }
}