Capture Knight

#include<iostream> using namespace std; #define N 1001 #define MAXQ 10000000 struct cell { int x, y; int dis; cell() {} cell(int x, int y, int dis) : x(x), y(y), dis(dis) {} }; cell qu[MAXQ]; int front, rear; int n,m; void Init() { front = 0; rear = 0; } bool Isempty() { if(front==rear) return true; return false; } void Push(cell x) { qu[rear++] = x; } cell Pop() { return qu[front++]; } bool isInside(int x, int y) { if (x < 1 || x > n || y < 1 || y > m) return false; return true; } int minStepToReachTarget(int knightPos[], int targetPos[]) { // x and y direction, where a knight can move int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2}; int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; Init(); // queue for storing states of knight in board // push starting position of knight with 0 distance Push(cell(knightPos[0], knightPos[1], 0)); cell t; int x, y; bool visit[N][N]; // make all cell unvisited for (int i = 1; i <= n; i++) for (int j = 1; j <=m; j++) visit[i][j] = false; // visit starting state visit[knightPos[0]][knightPos[1]] = true; while (!Isempty()) { t = Pop(); if (t.x == targetPos[0] && t.y == targetPos[1]) return t.dis; for (int i = 0; i < 8; i++) { x = t.x + dx[i]; y = t.y + dy[i]; if (isInside(x, y) && !visit[x][y]) { visit[x][y] = true; Push(cell(x, y, t.dis + 1)); } } } } int main() { int T; int knightPos[2], targetPos[2]; freopen("input.txt","r", stdin); cin >>T; int ans; for(int tc = 1; tc <=T; tc++) { cin >> n >> m; cin >> knightPos[0] >> knightPos[1]; cin >> targetPos[0]>>targetPos[1]; ans = minStepToReachTarget(knightPos,targetPos); cout <<"Case #"<<tc<<endl<< ans << endl; } return 0; }