#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main(){ int n; cin >> n; std::vector> stored_moves(n-1, std::vector(n-1, -1)); std::pair target(0,0); if(n < 5 || n> 25) return -1; for(int i=1; i> current_board(n, std::vector(n, false)); std::vector> last_board(n, std::vector(n, false)); std::vector new_x; std::vector new_y; new_x.push_back(n-1); new_y.push_back(n-1); current_board[n-1][n-1] = true; int while_count = 0; while(!current_board[0][0] && !new_x.empty()) { vector last_x = new_x; new_x.clear(); vector last_y = new_y; new_y.clear(); for(int k=0; k 0 && xpi < n) { if(ypj >= 0 && ypj < n && !current_board[xpi][ypj]) { new_x.push_back(xpi); new_y.push_back(ypj); current_board[xpi][ypj] = true; } if(ymj >= 0 && ymj < n && !current_board[xpi][ymj]) { new_x.push_back(xpi); new_y.push_back(ymj); current_board[xpi][ymj] = true; } } if(xmi >= 0 && xmi < n) { if(ypj >= 0 && ypj < n && !current_board[xmi][ypj]) { new_x.push_back(xmi); new_y.push_back(ypj); current_board[xmi][ypj] = true; } if(ymj >= 0 && ymj < n && !current_board[xmi][ymj]) { new_x.push_back(xmi); new_y.push_back(ymj); current_board[xmi][ymj] = true; } } // lazy: /* int xpj = x+j; int xmj = x-j; int ypi = y+i; int ymi = y-i;*/ xpi = x+j; xmi = x-j; ypj = y+i; ymj = y-i; if(xpi > 0 && xpi < n) { if(ypj >= 0 && ypj < n && !current_board[xpi][ypj]) { new_x.push_back(xpi); new_y.push_back(ypj); current_board[xpi][ypj] = true; } if(ymj >= 0 && ymj < n && !current_board[xpi][ymj]) { new_x.push_back(xpi); new_y.push_back(ymj); current_board[xpi][ymj] = true; } } if(xmi >= 0 && xmi < n) { if(ypj >= 0 && ypj < n && !current_board[xmi][ypj]) { new_x.push_back(xmi); new_y.push_back(ypj); current_board[xmi][ypj] = true; } if(ymj >= 0 && ymj < n && !current_board[xmi][ymj]) { new_x.push_back(xmi); new_y.push_back(ymj); current_board[xmi][ymj] = true; } } } while_count++; } if(current_board[0][0] == true) { stored_moves[i-1][j-1] = while_count; stored_moves[j-1][i-1] = while_count; } } } for(int i=0; i