#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ff first #define ss second #define mpa make_pair using namespace std; pair p1; bool check(int i, int j, int n) { if( (i<0) || (i>=n) || (j<0) || (j>=n) ) return false; return true; } int bfs(pair p1, int i, int j, int n) { queue< pair, int> > Q; map, bool> Board; Q.push(mpa(p1, 0)); while(!Q.empty()) { pair, int> temp = Q.front(); Q.pop(); if(temp.ff.ff == n-1 && temp.ff.ss == n-1) return temp.ss; int x = temp.ff.ff; int y = temp.ff.ss; int distance = temp.ss + 1; if(Board.count(mpa(x, y))) continue; Board[mpa(x, y)] = true; if( check(x + i, y + j, n) ) Q.push(mpa(mpa(x + i, y + j), distance)); if( check(x + i, y - j, n) ) Q.push(mpa(mpa(x + i, y - j), distance)); if( check(x - i, y + j, n) ) Q.push(mpa(mpa(x - i, y + j), distance)); if( check(x - i, y - j, n) ) Q.push(mpa(mpa(x - i, y - j), distance)); if( check(x + j, y + i, n) ) Q.push(mpa(mpa(x + j, y + i), distance)); if( check(x + j, y - i, n) ) Q.push(mpa(mpa(x + j, y - i), distance)); if( check(x - j, y + i, n) ) Q.push(mpa(mpa(x - j, y + i), distance)); if( check(x - j, y - i, n) ) Q.push(mpa(mpa(x - j, y - i), distance)); } return -1; } int main(){ int n; cin >> n; int ans[n][n] = {0}; p1.ff = 0; p1.ss = 0; for(int i=0; i