You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
bapc-prelim-2015/bapc-d.cpp

65 lines
1.6 KiB

#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using std::vector;
typedef vector<vector<char> > Board;
int check_white(Board &board, std::stack< std::pair<int, int> > &todo, int row, int col, int N) {
if (row >= 0 && col >= 0 && row < N && col < N) {
if (board[row][col] == '-') {
board[row][col] = 'w';
todo.push(std::make_pair(row, col));
return 1;
}
}
return 0;
}
int main(int argc, char const *argv[])
{
int T;
std::cin >> T;
for (int i = 0; i < T; ++i)
{
int N;
std::cin >> N;
Board board(N,vector<char>(N));
for (int row = 0; row < N; row++) {
char temp[N+1];
std::cin >> temp;
for(int col = 0; col < N; col++) {
board[row][col] = temp[col];
}
}
// fill stack with whites
std::stack< std::pair<int, int> > todo;
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (board[row][col] == 'w') {
todo.push(std::pair<int, int>(row, col));
}
}
}
int no_made_white = 0;
while(!todo.empty()) {
std::pair<int, int> n = todo.top();
todo.pop();
int row = n.first;
int col = n.second;
no_made_white += check_white(board, todo, row-1, col-1, N);
no_made_white += check_white(board, todo, row-1, col, N);
no_made_white += check_white(board, todo, row-1, col+1, N);
no_made_white += check_white(board, todo, row, col-1, N);
no_made_white += check_white(board, todo, row, col+1, N);
no_made_white += check_white(board, todo, row+1, col-1, N);
no_made_white += check_white(board, todo, row+1, col, N);
no_made_white += check_white(board, todo, row+1, col+1, N);
}
std::cout << no_made_white << std::endl;
}
return 0;
}