Go to diff to previous submission
#include <cstdio> #include <queue> #include <cstring> #include <string> using namespace std; struct Point { int a; int b; }; queue <Point> trace; int grid[200][200]; int a, b, a1, b1, a2, b2; bool push (Point next) { Point cur = trace.front(); if (next.a >= 0 && next.a < a && next.b >= 0 && next.b < b) { if (grid[cur.a][cur.b] + 1 < grid[next.a][next.b]) { trace.push (next); grid[next.a][next.b] = grid[cur.a][cur.b] + 1; if (next.a == a2 && next.b == b2) return true; } } return false; } int main() { while (scanf ("%d%d%d%d%d%d", &a, &b, &a1, &b1, &a2, &b2) == 6) { for (int i = 0; i < 200; i++) for (int j = 0; j < 200; j++) grid[i][j] = 1000000000; a1--; b1--; a2--; b2--; Point start; start.a = a1; start.b = b1; grid[a1][b1] = 0; trace.push (start); while (!trace.empty()) { Point cur = trace.front(); Point next; next.a = cur.a - 2; next.b = cur.b - 1; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a - 2; next.b = cur.b + 1; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a + 2; next.b = cur.b - 1; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a + 2; next.b = cur.b + 1; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a - 1; next.b = cur.b - 2; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a - 1; next.b = cur.b + 2; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a + 1; next.b = cur.b - 2; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } next.a = cur.a + 1; next.b = cur.b + 2; if (push (next)) { printf ("%d\n", grid[next.a][next.b]); goto next; } trace.pop(); } printf ("impossible\n"); next:; while (!trace.empty()) trace.pop(); } return 0; }