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;
}