#include <iostream> #include <stdio.h> #include <vector> using namespace std; class Point { private: unsigned int x; unsigned int y; public: Point(unsigned int _x, unsigned int _y) { this->x = _x; this->y = _y; } unsigned int getX() { return this->x; } unsigned int getY(){ return this->y; } }; bool isInMoves(vector< vector<bool> > board, vector< vector< vector<bool> > > moves) { unsigned long long int i = 0; for(i = 0 ; i < moves.size(); i++) { if(board == moves[i]) { return true; } } return false; } vector<Point> findPossibleMoves(vector< vector<bool> > board) { vector<Point> points; unsigned int i = 0; unsigned int j = 0; for(i = 0 ; i < board.size(); i++) { for(j = 0 ; j < board.size(); j++) { if(board[i][j] == false && ((i > 0 && board[i-1][j] == true) || (i < board.size()-1 && board[i+1][j] == true) || (j > 0 && board[i][j-1] == true) || (j < board.size()-1 && board[i][j+1] == true))){ points.push_back(Point(i, j)); } } } return points; } void makeMove(vector< vector<bool> > board, vector< vector< vector<bool> > > &moves, unsigned int k) { if(k == 0 && !isInMoves(board, moves)) { moves.push_back(board); } else if(k > 0){ vector<Point> points = findPossibleMoves(board); unsigned long long int i = 0; unsigned int t = k - 1; for(i = 0; i < points.size(); i++) { Point p = points[i]; vector< vector<bool> >b = board; b[p.getX()][p.getY()] = true; makeMove(b, moves, t); } } } int main() { unsigned int i = 0; unsigned int j = 0; unsigned int n; unsigned int k; char c; scanf("%d %d", &n, &k); vector< vector<bool> > board; vector< vector< vector<bool> > > moves; board.resize(n); for(i = 0 ; i < n; i++) { board.at(i).resize(n); for(j = 0 ; j < n; j++) { scanf("%c", &c); if(c == '\n') { scanf("%c", &c); } if(c == '#') { board[i][j] = true; } else { board[i][j] = false; } } } makeMove(board, moves, k); cout << moves.size() % 1000000007; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include <iostream> #include <stdio.h> #include <vector> using namespace std; class Point { private: unsigned int x; unsigned int y; public: Point(unsigned int _x, unsigned int _y) { this->x = _x; this->y = _y; } unsigned int getX() { return this->x; } unsigned int getY(){ return this->y; } }; bool isInMoves(vector< vector<bool> > board, vector< vector< vector<bool> > > moves) { unsigned long long int i = 0; for(i = 0 ; i < moves.size(); i++) { if(board == moves[i]) { return true; } } return false; } vector<Point> findPossibleMoves(vector< vector<bool> > board) { vector<Point> points; unsigned int i = 0; unsigned int j = 0; for(i = 0 ; i < board.size(); i++) { for(j = 0 ; j < board.size(); j++) { if(board[i][j] == false && ((i > 0 && board[i-1][j] == true) || (i < board.size()-1 && board[i+1][j] == true) || (j > 0 && board[i][j-1] == true) || (j < board.size()-1 && board[i][j+1] == true))){ points.push_back(Point(i, j)); } } } return points; } void makeMove(vector< vector<bool> > board, vector< vector< vector<bool> > > &moves, unsigned int k) { if(k == 0 && !isInMoves(board, moves)) { moves.push_back(board); } else if(k > 0){ vector<Point> points = findPossibleMoves(board); unsigned long long int i = 0; unsigned int t = k - 1; for(i = 0; i < points.size(); i++) { Point p = points[i]; vector< vector<bool> >b = board; b[p.getX()][p.getY()] = true; makeMove(b, moves, t); } } } int main() { unsigned int i = 0; unsigned int j = 0; unsigned int n; unsigned int k; char c; scanf("%d %d", &n, &k); vector< vector<bool> > board; vector< vector< vector<bool> > > moves; board.resize(n); for(i = 0 ; i < n; i++) { board.at(i).resize(n); for(j = 0 ; j < n; j++) { scanf("%c", &c); if(c == '\n') { scanf("%c", &c); } if(c == '#') { board[i][j] = true; } else { board[i][j] = false; } } } makeMove(board, moves, k); cout << moves.size() % 1000000007; return 0; } |