글 읽기 - 테스트 케이스 질문입니다!

yenik 6년 전 1

입력2의 결과가 9라고 나와있는데 언제 9가 되는지 못찾겠습니다ㅠ

4 6
0 0 0 0 0 3
1 0 0 0 3 2
1 1 1 3 0 2
0 0 0 0 0 2

벽을 3이라고 했을 때 안전한 지대가 8인것 까지는 찾겠는데 9인걸 못찾게습니다ㅜ

코딩한 답도 8이라고 나와서요

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int a[8][8];
bool check[8][8];
int n, m;

vector <pair<int, int> > virus;

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

int maxx=0;
int block = 0;
int cnt = 0;

void expendVirus() {
	memset(check, false, sizeof(check));

	cnt = 0;
	for (int i = 0; i < virus.size(); i++) {
		int sx = virus[i].first;
		int sy = virus[i].second;

		queue<pair<int, int> >q;

		q.push(make_pair(sx, sy));
		check[sx][sy] = true;

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

			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k]; int ny = y + dy[k];
				if (0 <= nx && nx < n && 0 <= ny && ny < m) {
					if (!check[nx][ny] && a[nx][ny] == 0) {
						check[nx][ny] = true;
						q.push(make_pair(nx, ny));
					}
				}
			}

		}


	}
	cnt = n*m - cnt - block-3;
	maxx = (maxx > cnt ? maxx : cnt);

}

int main()
{

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 2) {
				virus.push_back(make_pair(i, j));
			}
			if (a[i][j] == 1) block++;
		}
	}

	for (int i = 0; i < n*m-2; i++) {
		pair<int,int> b1, b2, b3;
		if (a[i/n][i - (i / n)*n] != 0) continue;
		b1.first = i / n;
		b1.second = i - (i / n)*n;

		for (int j = i+1; j < n*m-1; j++) {
			if (a[j / n][j - (j / n)*n] != 0) continue;
			b2.first = j / n;
			b2.second = j - (j / n)*n;

			for (int k = j+1; k < n*m; k++) {
				if (a[k / n][k - (k / n)*n] != 0) continue;
				b3.first = k / n;
				b3.second = k - (k / n)*n;

				a[b1.first][b1.second] = 1;
				a[b2.first][b2.second] = 1;
				a[b3.first][b3.second] = 1;
				expendVirus();
				a[b1.first][b1.second] = 0;
				a[b2.first][b2.second] = 0;
				a[b3.first][b3.second] = 0;

			}
		}

	}

	cout << maxx << '\n';

	return 0;
}

djm03178 6년 전 2

0 0 0 0 3 0

1 0 0 3 0 2

1 1 1 0 0 2

0 0 0 3 0 2

이렇게 막으면 9칸이 안전해집니다.

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

문제

문제

출처

ICPC

테스트 케이스 질문입니다!

yenik 6년 전 1

djm03178 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말