알고리즘 공부
백준 양
컴퓨터과학
2023. 7. 21. 00:31
https://www.acmicpc.net/problem/3184
3184번: 양
첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.
www.acmicpc.net
흠 dfs 문제로 풀려고 해도 전부 bfs로 풀리네요 흐음
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
using namespace std;
struct Point {
int i, j, t, cnt;
char c;
};
void Prints(vector<vector<int>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<char>>maps, int n, int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<char>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<vector<bool>>>maps, int n, int m, int k) {
for (int t = 0; t < k; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maps[t][i][j];
}
cout << endl;
}
cout << endl;
}
cout << endl;
}
struct Data {
int score;
int index;
};
struct Word {
std::string word;
int count;
};
bool compare(const Data &a, const Data &b) {
return a.score > b.score;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<char>>maps;
vector<bool>tmpbVisited(m,false);
vector<vector<bool>>bVisited(n, tmpbVisited);
vector<vector<bool>>initbVisited(n, tmpbVisited);
for (int i = 0; i < n; i++) {
string str;
cin >> str;
vector<char>tmpMaps;
for (int j = 0; j < str.size(); j++) {
if (str[j] == '#') {
initbVisited[i][j] = true;
}
tmpMaps.push_back(str[j]);
}
maps.push_back(tmpMaps);
}
int diri[] = { 1,-1,0,0 };
int dirj[] = { 0,0,1,-1 };
bVisited = initbVisited;
int gsheep = 0;
int gwolf = 0;
for (int z = 0; z < n; z++) {
for (int t = 0; t < m; t++) {
int sheep = 0;
int wolf = 0;
if (bVisited[z][t] == false ) {
queue<Point>q;
Point p;
p.i = z;
p.j = t;
bVisited[z][t] = true;
if (maps[z][t] == 'o') {
//cout << z<<","<<t<<endl;
sheep++;
}
if (maps[z][t] == 'v') {
//cout << z << "," << t << endl;
wolf++;
}
q.push(p);
while (!q.empty()) {
Point start = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int tmpDiri = start.i + diri[i];
int tmpDirj = start.j + dirj[i];
if (tmpDiri == -1 || tmpDirj == -1 || tmpDiri >= n || tmpDirj >= m||bVisited[tmpDiri][tmpDirj]==true) {
continue;
}
bVisited[tmpDiri][tmpDirj] = true;
Point tmpP;
tmpP.i = tmpDiri;
tmpP.j = tmpDirj;
q.push(tmpP);
if (maps[tmpDiri][tmpDirj] == 'o') {
// cout << tmpDiri << "," << tmpDirj << endl;
sheep++;
}
if (maps[tmpDiri][tmpDirj] == 'v') {
//cout << tmpDiri << "," << tmpDirj << endl;
wolf++;
}
//Prints(bVisited, n, m);
}
}
}
if (sheep > 0 || wolf > 0) {
if (sheep > wolf) {
//cout << "sheep win:"<<sheep << endl;
gsheep += sheep;
}
else if (sheep <= wolf) {
//cout <<"wolf win:"<< wolf << endl;
gwolf += wolf;
}
}
}
}
cout << gsheep << " " << gwolf;
return 0;
}