알고리즘 공부
백준 Puyo Puyo
컴퓨터과학
2023. 7. 13. 19:57
https://www.acmicpc.net/problem/11559
11559번: Puyo Puyo
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
www.acmicpc.net
ㅠㅠ 어렵네요 골드는 휴 ㅠㅠㅠ 그래도 풀었습니다 ㅎ ㅠ
먼저 음 터지는 부분구현 후 -> 터진 이후에 뿌요를 내려준다음 터지면 무조건 내려서 잇을때까지 확인햇습니다 ㅎ
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
void Prints(vector<vector<char>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
struct Point {
int m;
int n;
};
struct Data {
int index;
int cnt;
};
void confirm(queue<Point>& q, int startm, int startn, vector<vector<bool>>& bVisited, vector<vector<char>>maps, char color, int m, int n,int & crashCnt, vector<Point>&saveCrash) {
int dirM[] = { 0,0,1,-1 };
int dirN[] = { 1,-1,0,0 };
for (int i = 0; i < 4; i++) {
int tmpdirM = startm + dirM[i];
int tmpdirN = startn + dirN[i];
if (tmpdirM == -1 || tmpdirN == -1 || tmpdirM >= m || tmpdirN >= n) {
continue;
}
if (maps[tmpdirN][tmpdirM] == color && bVisited[tmpdirN][tmpdirM] == false) {
bVisited[tmpdirN][tmpdirM] = true;
Point tmpp;
tmpp.m = tmpdirM;
tmpp.n = tmpdirN;
q.push(tmpp);
saveCrash.push_back(tmpp);
crashCnt++;
}
}
return;
}
int main() {
int n = 12;
int m = 6;
//r g b p y
//4개 이상일 때 터진다
//
int boomCnt = 0;
vector<vector<char>>maps;
vector<bool>tmpVisited(m, false);
vector<vector<bool>>bVisited(n, tmpVisited);
for (int i = 0; i < n; i++) {
string str;
cin >> str;
vector<char>tmpMaps;
for (int j = 0; j < m; j++) {
tmpMaps.push_back(str[j]);
//tmpMaps.push_back(tmpStr[i][j]);
if (str[j] == '.') {
bVisited[i][j] = true;
}
}
maps.push_back(tmpMaps);
}
bool bBoomb = true;
//검사모드
while (bBoomb) {
bBoomb = false;
for (int k = m - 1; k >= 0; k--) {
queue<Point>checkSum;
for (int z = n - 1; z >= 0; z--) {
if (bVisited[z][k] == true) {
Point p;
p.m = k;
p.n = z;
checkSum.push(p);
}
else if (bVisited[z][k] == false) {
if (checkSum.size() > 0) {
Point start = checkSum.front();
if (z < start.n) {
int tmpChar = maps[z][k];
maps[z][k] = maps[start.n][start.m];
maps[start.n][start.m] = tmpChar;
bVisited[z][k] = true;
bVisited[start.n][start.m] = false;
Point p;
p.m = k;
p.n = z;
checkSum.pop();
checkSum.push(p);
}
}
}
}
}
//crash
char color[5] = { 'R','G','B','P','Y' };
vector<Point>saveCrash;
int crashCnt = 1;
for (int z = n - 1; z >= 0; z--) {
for (int k = m - 1; k >= 0; k--) {
Point p;
p.m = k;
p.n = z;
if (bVisited[z][k] == false) {
queue<Point> q;
q.push(p);
bVisited[z][k] = true;
char crash = 'z';
while (!q.empty()) {
Point start = q.front();
q.pop();
if (crash != maps[start.n][start.m]) {
if (crashCnt >= 4) {
for (int u = 0; u < saveCrash.size(); u++) {
maps[saveCrash[u].n][saveCrash[u].m] = '.';
}
bBoomb = true;
}
else {
for (int u = 0; u < saveCrash.size(); u++) {
bVisited[saveCrash[u].n][saveCrash[u].m] = false;
}
}
saveCrash.clear();
crash = maps[start.n][start.m];
crashCnt = 1;
//cout << crashCnt << endl;
Point tmpP;
tmpP.m = start.m;
tmpP.n = start.n;
saveCrash.push_back(tmpP);
}
switch (maps[start.n][start.m])
{
case 'R':
confirm(q, start.m, start.n, bVisited, maps, 'R', m, n, crashCnt, saveCrash);
if (crashCnt >= 4) {
bBoomb = true;
}
else {
}
if (crash != maps[start.n][start.m]) {
crash = maps[start.n][start.m];
crashCnt = 1;
}
break;
case 'G':
//cout << maps[start.n][start.m] << "," << endl;
confirm(q, start.m, start.n, bVisited, maps, 'G', m, n, crashCnt, saveCrash);
if (crashCnt >= 4) {
bBoomb = true;
}
if (crash != maps[start.n][start.m]) {
crash = maps[start.n][start.m];
crashCnt = 1;
}
break;
case 'B':
confirm(q, start.m, start.n, bVisited, maps, 'B', m, n, crashCnt, saveCrash);
if (crashCnt >= 4) {
bBoomb = true;
}
if (crash != maps[start.n][start.m]) {
crash = maps[start.n][start.m];
crashCnt = 1;
}
break;
case 'P':
confirm(q, start.m, start.n, bVisited, maps, 'P', m, n, crashCnt, saveCrash);
if (crashCnt >= 4) {
bBoomb = true;
}
if (crash != maps[start.n][start.m]) {
crash = maps[start.n][start.m];
crashCnt = 1;
}
break;
case 'Y':
confirm(q, start.m, start.n, bVisited, maps, 'Y', m, n, crashCnt, saveCrash);
if (crashCnt >= 4) {
bBoomb = true;
}
if (crash != maps[start.n][start.m]) {
crash = maps[start.n][start.m];
crashCnt = 1;
}
break;
default:
break;
}
}
}
}
}
//last
if (crashCnt >= 4) {
bBoomb = true;
}
else {
for (int u = 0; u < saveCrash.size(); u++) {
bVisited[saveCrash[u].n][saveCrash[u].m] = false;
}
}
if (bBoomb == true) {
boomCnt++;
}
}
cout << boomCnt;
return 0;
}