#include #include #include using namespace std; struct Position { int row; int col; }; struct Memo { bool bVisited; int iMoves; }; int g_BoardSize = 0; int g_len1 = 0; int g_len2 = 0; Memo g_Memo[25][25] = { 0 }; int g_maxMoves = 0; #define min(a,b) ((a)<(b)?(a):(b)) struct SearchNode { Position curr; //Position prev; int moves_taken; }; queue g_frontier; bool isValidMove( int posr, int posc ) { return ((posr >= 0) && (posr < g_BoardSize) && (posc >= 0) && (posc < g_BoardSize)); } int numMoves( int i, int j ) { SearchNode node = { 0 }; g_frontier.push( node ); g_Memo[0][0].bVisited = true; while( !g_frontier.empty() ) { SearchNode examine = g_frontier.front(); g_frontier.pop(); int posr = examine.curr.row; int posc = examine.curr.col; Position possible_moves[8] = { { posr + i, posc + j }, { posr + i, posc - j }, { posr - i, posc + j }, { posr - i, posc - j }, { posr + j, posc + i }, { posr + j, posc - i }, { posr - j, posc + i }, { posr - j, posc - i }, }; int num_moves = (i == j) ? 4 : 8; for( int i = 0; i < num_moves; i++ ) { int nextr = possible_moves[i].row; int nextc = possible_moves[i].col; if( (nextr == g_BoardSize - 1) && (nextc == g_BoardSize - 1) ){ return examine.moves_taken + 1; } if( !isValidMove(nextr, nextc) ) { continue; } if( g_Memo[nextr][nextc].bVisited ) { continue; } g_Memo[nextr][nextc].bVisited = true; SearchNode nextNode = { { nextr, nextc }, //{ posr, posc }, examine.moves_taken + 1 }; g_frontier.push( nextNode ); } } return g_maxMoves; } int numMoves( int posr, int posc, int moves_taken ) { if( (posr == g_BoardSize - 1) && (posc == g_BoardSize - 1) ){ return 0; } if( //g_Memo[posr][posc].bVisited || (moves_taken >= g_maxMoves) ) { return g_maxMoves; } if( 0 != g_Memo[posr][posc].iMoves ) { return g_Memo[posr][posc].iMoves; } Position possible_moves[8] = { { posr + g_len1, posc + g_len2 }, { posr + g_len1, posc - g_len2 }, { posr - g_len1, posc + g_len2 }, { posr - g_len1, posc - g_len2 }, { posr + g_len2, posc + g_len1 }, { posr + g_len2, posc - g_len1 }, { posr - g_len2, posc + g_len1 }, { posr - g_len2, posc - g_len1 }, }; int num_moves = (g_len1 == g_len2) ? 4 : 8; int min_moves = g_maxMoves; g_Memo[posr][posc].bVisited = true; bool bSkipped = true; for( int i = 0; i < num_moves; i++ ) { int nextr = possible_moves[i].row; int nextc = possible_moves[i].col; if( !isValidMove(nextr, nextc) ) { continue; } if( g_Memo[nextr][nextc].bVisited ) { continue; } bSkipped = false; int num_moves = numMoves( nextr, nextc, moves_taken + 1 ); min_moves = min( min_moves, num_moves ); } g_Memo[posr][posc].bVisited = false; //if( min_moves < g_maxMoves ) if( !bSkipped ) g_Memo[posr][posc].iMoves = min_moves + 1; return min_moves + 1; } void clearBoard() { for( int i = 0; i < g_BoardSize; i++ ) { for( int j = 0; j < g_BoardSize; j++ ) { //g_Memo[i][j].iMoves = 0; g_Memo[i][j].bVisited = false; } } } void printBoard() { for( int i = 0; i < g_BoardSize; i++ ) { for( int j = 0; j < g_BoardSize; j++ ) { printf("%5d", g_Memo[i][j].iMoves); } cout << "\n"; } } int main(){ cin >> g_BoardSize; g_maxMoves = g_BoardSize * g_BoardSize / 2; int g_Answers[25][25] = { 0 }; int i = 1; for( ; i < g_BoardSize; i++ ) { for( int j = i; j < g_BoardSize; j++ ) { clearBoard(); while( !g_frontier.empty() ) { g_frontier.pop(); } //g_len1 = i; //g_len2 = j; g_Answers[i][j] = numMoves( i, j ); if( g_Answers[i][j] >= g_maxMoves ) { g_Answers[i][j] = -1; } //cout << "i = " << i << ", j = " << j << "\n"; //printBoard(); } } for( i = 1; i < g_BoardSize; i++ ) { for( int j = 1; j < g_BoardSize; j++ ) { if( j >= i ) { cout << g_Answers[i][j] << " "; } else { cout << g_Answers[j][i] << " "; } } cout << "\n"; } return 0; }