글 읽기 - 반례를 잘 모르겠습니다. 바로 틀렸다고 나옵니다.

cleankid99 5년 전 1

bfs를 이용하여 풀었습니다.

비주얼 스튜디오상에서는 예제와 질문글에 있는 반례 모두 잘 나오는데

넣자마자 틀렸다고 나오네요..

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

const int dy[] = { 0,0,-1,1 };
const int dx[] = { 1,-1,0,0 };

vector<vector<char> > a;
vector<vector<int> > chk1;
vector<vector<char> > b;
vector<vector<int> > chk2;

int main() {
	string str;
	int n, cnt=0;
	cin >> n;
	a.resize(n + 1);
	chk1.resize(n + 1);
	b.resize(n + 1);
	chk2.resize(n + 1);

	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < n; j++) {
			if (str[j] == 'G') {
				a[i].push_back(str[j]);
				chk1[i].push_back(0);
				b[i].push_back('R');
				chk2[i].push_back(0);
			}
			else {
				a[i].push_back(str[j]);
				chk1[i].push_back(0);
				b[i].push_back(str[j]);
				chk2[i].push_back(0);
			}			
		}
	}

	queue<pair<int, int> > q;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			if (chk1[i][j] == 0) {
				char search = a[i][j];
				q.push(make_pair(i, j));
				chk1[i][j] = 1;

				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x, ny = y;
						nx += dx[k];
						ny += dy[k];

						if (nx >= 0 && nx < n && ny >= 0 && ny < n && chk1[nx][ny] == 0 && a[nx][ny] == search) {
							q.push(make_pair(nx, ny));
							chk1[nx][ny] = 1;
						}

					}

				}
				cnt++;
			}
			
		}
	}

	cout << cnt << " ";

	cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			if (chk2[i][j] == 0) {
				char search = a[i][j];
				q.push(make_pair(i, j));
				chk2[i][j] = 1;

				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x, ny = y;
						nx += dx[k];
						ny += dy[k];

						if (nx >= 0 && nx < n && ny >= 0 && ny < n && chk2[nx][ny] == 0 && b[nx][ny] == search) {
							q.push(make_pair(nx, ny));
							chk2[nx][ny] = 1;
						}

					}

				}
				cnt++;
			}
			
		}
	}

	cout << cnt << '\n';

	return 0;
}

cleankid99 5년 전 0

오타 하나 찾아서 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 잘 모르겠습니다. 바로 틀렸다고 나옵니다.

cleankid99 5년 전 1

cleankid99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말