KnightsTour
日課消化。始めから綺麗にコードが書けるようになりたい。
問題自体は難しくない。実装が面倒なだけ。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; #define FOR(i,s,e) for (int i = int(s); i != int(e); i++) #define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ISEQ(c) (c).begin(), (c).end() class KnightsTour { private: vector<string> table; int row; int col; int tmp_row; int tmp_col; int ablenum; int total_cell; bool accessible_cell(int i, int j)const{ if(i<0 || i>=table.size()) return false; if(j<0 || j>=table.size()) return false; if(table[i][j] == '*') return false; else return true; } int accessible_num(int row, int col){ int num=0; if(accessible_cell(row-2,col-1)) num++; if(accessible_cell(row-2,col+1)) num++; if(accessible_cell(row-1,col-2)) num++; if(accessible_cell(row-1,col+2)) num++; if(accessible_cell(row+1,col-2)) num++; if(accessible_cell(row+1,col+2)) num++; if(accessible_cell(row+2,col-1)) num++; if(accessible_cell(row+2,col+1)) num++; return num; } void compare_accessible(int row, int col){ if(accessible_cell(row,col)){ if(ablenum > accessible_num(row,col)){ ablenum = accessible_num(row,col); tmp_row = row; tmp_col = col; } } } public: int visitedPositions(vector<string> board) { table = board; total_cell = 1; for(unsigned int i=0; i<board.size(); i++){ string::size_type index = board[i].find('K'); if(index != string::npos){ row = i; col = index; break; } } while(1){ ablenum = 9; table[row][col] = '*'; compare_accessible(row-2,col-1); compare_accessible(row-2,col+1); compare_accessible(row-1,col-2); compare_accessible(row-1,col+2); compare_accessible(row+1,col-2); compare_accessible(row+1,col+2); compare_accessible(row+2,col-1); compare_accessible(row+2,col+1); if(ablenum == 9) break; row = tmp_row; col = tmp_col; total_cell++; if(ablenum == 0) break; } return total_cell; } };