백준 3187번 양치기 꿍 C++

https://www.acmicpc.net/problem/3187

3187번: 양치기 꿍

 

bfs

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using int64 = long long;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int r, c;
vector<vector<char>> board;
vector<vector<bool>> found;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c;
	board = vector<vector<char>>(r, vector<char>(c));
	found = vector<vector<bool>>(r, vector<bool>(c, false));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> board[i][j];
		}
	}
	int totalV = 0;
	int totalK = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == '#') continue;
			if (found[i][j]) continue;
			queue<pair<int, int>> q;
			q.push({ i,j });
			found[i][j] = true;
			int v = 0;
			int k = 0;
			while (!q.empty()) {
				auto curr = q.front();
				q.pop();
				if (board[curr.first][curr.second] == 'v') v++;
				else if (board[curr.first][curr.second] == 'k') k++;
				for (int k = 0; k < 4; k++) {
					int nextRow = curr.first + dRow[k];
					int nextCol = curr.second + dCol[k];
					if (nextRow >= r || nextRow < 0) continue;
					if (nextCol >= c || nextCol < 0) continue;
					if (board[nextRow][nextCol] == '#') continue;
					if (found[nextRow][nextCol]) continue;
					found[nextRow][nextCol] = true;
					q.push({ nextRow,nextCol });
				}
			}
			if (k > v) totalK += k;
			else totalV += v;
		}
	}
	cout << totalK << " " << totalV;
};