글 읽기 - 도와주세요

tdj03063 3년 전 0

게시판에 있는 반례는 다 통과하는 것 같은데 왜 틀리는지 모르겠습니다. ㅜㅜ

#include <cstring> // memset
#include <string> //string
#include <iostream> 
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
#define MAX 300

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)

int N, M;
int arr[MAX][MAX] = { 0, };
int temp[MAX][MAX] = { 0, };
bool visit[MAX][MAX] = { false, };
bool check = true;
queue<pair<int, int> > q;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int result = 0;

void dfs(int y, int x) {
	visit[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int nexty = y + dy[i];
		int nextx = x + dx[i];


		if (!visit[nexty][nextx] && arr[nexty][nextx] > 0) {
			dfs(nexty, nextx);
		}
	}
}

void bfs() {
	while (!q.empty()) {
		int qsize = q.size();
		int count = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (!visit[i][j] && arr[i][j]) {
					dfs(i, j);
					count++;
				}

		if (count >= 2) {
			cout << result;
			return;
		}
		if (count == 0) {
			cout << "0";
			return;
		}
		memset(visit, false, sizeof(visit));

		while (qsize--) {
			int x = q.front().second;
			int y = q.front().first;
			q.pop();

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

				if (arr[ny][nx] <= 0) cnt++;
				if (!visit[ny][nx] && arr[ny][nx] > 0) {
					q.push(make_pair(ny, nx));
					visit[ny][nx] = true;
					//cout << "q : (" << ny << ", " << nx << ")  ";
				}
			}
			temp[y][x] += cnt;
			if (cnt == 4) {
				check = false;
			}
		}

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				arr[i][j] -= temp[i][j];

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (arr[i][j] < 0) arr[i][j] = 0;

		result++;
		memset(visit, false, sizeof(visit));
		memset(temp, 0, sizeof(visit));
	}
	cout << "0";
}

int main() {
	fastio;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
			if (!arr[i][j] == 0)
				q.push(make_pair(i, j));
		}

	bfs();
}

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

문제

문제

출처

ICPC

도와주세요

tdj03063 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말