UVa 439 Knight Moves

AI Translated from Chinese

First time writing a solution ~

Simple, but got stuck for a while. Finally realized I forgot to zero the array XD

Problem: Luogu UVa439

Problem Statement

Input two coordinates on an 8×8 chessboard (start and end points. Column: ah, Row: 18). Find the minimum number of moves a Knight needs to get from start to end.

Analysis

Typical BFS shortest path problem. 2D array id[10][10] stores the step count after taking one more step from this cell. Queues qx, qy store coordinates.

Note that each cell cannot be visited repeatedly, otherwise the shortest path cannot be calculated.

Code

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
// Offsets: eight directions a knight can move
const int dx[8] = {-1,-2,-2,-1,1,2,2,1};
const int dy[8] = {2,1,-1,-2,-2,-1,1,2};
int id[10][10];

int bfs(int x, int y, int x_target, int y_target) {
    if (x == x_target && y == y_target) return 0;  // Start equals end
    queue<int> qx, qy;
    qx.push(x), qy.push(y);
    id[x][y] = 1;
    while (1) {
        x = qx.front(), y = qy.front();
        for (int i = 0; i < 8; i++) {
            int newx = x + dx[i], newy = y + dy[i];
            if (newx == x_target && newy == y_target) return id[x][y];
            if (newx < 1 || newy < 1 || newx > 8 || newy > 8 || id[newx][newy])  // Out of bounds or already visited
                continue;
            qx.push(newx), qy.push(newy);
            id[newx][newy] = id[x][y] + 1;
        }
        qx.pop(), qy.pop();
    }
}

int main() {
#ifdef LOCAL
    freopen("knight_moves.in", "r", stdin);
    freopen("knight_moves.out", "w", stdout);
#endif
    string start, target;
    while (cin >> start >> target && start.length() && target.length()) {
        memset(id, 0, sizeof(id));  // Remember to zero!
        cout<<"To get from "<<start<<" to "<<target<<" takes ";
        cout<<bfs(start[1]-'0', start[0]-'a'+1, target[1]-'0', target[0]-'a'+1)<<" knight moves.\n";
    }
}

P.S. Tips

You may have noticed that I used redirected I/O but didn’t define the LOCAL symbol in the code — actually I compiled it in the compilation options.

The benefit of this is that during local debugging, redirected I/O is the default, and when submitting to OJ, the redirected code is automatically ignored. Convenient and avoids errors.

Just add -DLOCAL parameter during compilation. My approach was to modify Sublime Text’s build system file:

c++_acm.sublime-build

{
   "shell_cmd": "g++ -finput-charset=UTF-8 -fexec-charset=GBK -Wall -DLOCAL \"${file_name}\" -o \"${file_base_name}\" && ${file_base_name} && echo Press ENTER to continue...",
   "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
   "working_dir": "${file_path}",
   "selector": "source.c++",
   "encoding": "gbk",
   "variants":
   [
       {
           "name": "Single File Build & Run in cmd",
           "shell_cmd": "g++ -finput-charset=UTF-8 -fexec-charset=GBK -g -Wall \"${file_name}\" -o \"${file_base_name}\" && start cmd /c \"\"${file_base_name}\" & pause\""
       }
   ]
}

Press Ctrl + Shift + B, which shows two compilation options. The first is redirected, the second uses terminal window for standard I/O.

Redirected I/O is great to use once, and always great to keep using (