Given an n × m chessboard (with 1 < n, m ≤ 400) and the starting position of a knight, determine the minimum number of moves required for the knight to reach every other square. If a square is unreachable, output -1.

Input Format

A single line containing four integers: n, m, start_x, and start_y.

Output Format

Print an n × m matrix. Each value must be left-aligned and occupy a field width of 5 characters. Unreachable squares are represented by -1.

Example

Input:

3 3 1 1

Output:

0    3    2    
3    -1   1    
2    1    4    

Both Depth-First Search (DFS) with pruning and Breadth-First Search (BFS) can solve this problem. BFS is generally preferred for finding shortest paths in unweighted grids.

DFS Approach with Pruning

This implementation uses recursion to explore paths. A depth limit and comparison with existing distances are used to prune the search tree and avoid Time Limit Exceeded (TLE) errors.

#include <bits/stdc++.h>
#define LOOP(i, start, end) for (int i = start; i <= end; ++i)
#define MAX 410
using namespace std;

int rows, cols, startR, startC;
int dist[MAX][MAX];
int movesR[8] = {2, 2, 1, -1, -2, -2, 1, -1};
int movesC[8] = {1, -1, 2, 2, 1, -1, -2, -2};

void dfsExplore(int r, int c, int steps) {
    if (steps > 200) return;
    dist[r][c] = steps;
    
    LOOP(i, 0, 7) {
        int nr = r + movesR[i];
        int nc = c + movesC[i];
        if (nr >= 1 && nr <= rows && nc >= 1 && nc <= cols) {
            if (dist[nr][nc] == -1 || dist[nr][nc] > steps + 1) {
                dfsExplore(nr, nc, steps + 1);
            }
        }
    }
}

int main() {
    cin >> rows >> cols >> startR >> startC;
    memset(dist, -1, sizeof(dist));
    dfsExplore(startR, startC, 0);
    
    LOOP(i, 1, rows) {
        LOOP(j, 1, cols) {
            printf("%-5d", dist[i][j]);
        }
        printf("\n");
    }
    return 0;
}

BFS Approach

This solution uses a queue to systematically explore the board layer by layer, ensuring the first time a square is visited, it is via the shortest path.

#include <bits/stdc++.h>
#define LOOP(i, start, end) for (int i = start; i <= end; ++i)
#define MAX 410
using namespace std;

int rows, cols, startR, startC;
int dist[MAX][MAX];
int movesR[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int movesC[8] = {2, -2, 2, -2, 1, -1, 1, -1};
queue<int> qR, qC;

void bfsExplore(int r, int c) {
    dist[r][c] = 0;
    qR.push(r);
    qC.push(c);
    
    while (!qR.empty()) {
        int curR = qR.front(); qR.pop();
        int curC = qC.front(); qC.pop();
        
        LOOP(i, 0, 7) {
            int nr = curR + movesR[i];
            int nc = curC + movesC[i];
            
            if (nr < 1 || nr > rows || nc < 1 || nc > cols) continue;
            if (dist[nr][nc] != -1) continue;
            
            dist[nr][nc] = dist[curR][curC] + 1;
            qR.push(nr);
            qC.push(nc);
        }
    }
}

int main() {
    cin >> rows >> cols >> startR >> startC;
    memset(dist, -1, sizeof(dist));
    bfsExplore(startR, startC);
    
    LOOP(i, 1, rows) {
        LOOP(j, 1, cols) {
            printf("%-5d", dist[i][j]);
        }
        printf("\n");
    }
    return 0;
}