글 읽기 - 작은 입력에 대해선 답이 나오는것 같은데 좀만 커져도 안돼요.

devbelly 4년 전 0

재귀적으로 벽을 고른 후

3개의 벽을 다 세웠다면

bfs수행을 위한 visited 배열을 초기화 한후 바이러스들을 bfs 수행했습니다

예제도 안나오는데 어디를 수정하면 될까요?

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
int board[8][8];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m;
bool visited[8][8];
int ans = 0;
int aa; //1
int bb; //2
int cc;//0

int bfs(int y, int x) {
	if (visited[y][x]) return 0;
	visited[y][x] = true;
	
	int cnt = 1;
	queue<p> q;
	q.emplace(y, x);
	while (!q.empty()) {
		
		auto [y, x] = q.front();
		q.pop();
		for (int i = 0;i < 4;++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (board[ny][nx] == 1) continue;
			if (!visited[ny][nx] && board[ny][nx] == 0) {
				visited[ny][nx] = true;
				q.emplace(ny, nx);
				++cnt; // 감염/
			}
		}
	}
	
	return cnt;
}
void makeWall(int cnt,int y,int x) {
	
	if (cnt == 0) {
		int ret = 0;
		memset(visited, 0, sizeof(visited));
		for(int i=0;i<n;++i)
			for (int j = 0;j < m;++j) {
				if (board[i][j] == 2)
					ret += bfs(i, j);
			}
		ans = max(ans,n*m-ret-aa); //전체크기 - ret(바이러스총수)-aa(벽갯수)
		
	}

	for(int i=y;i<n;++i)
		for (int j = 0;j < m;++j) {
			if (i<0||i>=n||j<0||j>=m) continue;	
			if (board[i][j] == 0) {
				++aa; //벽 증가
				--cc; // 빈공간 감소
				board[i][j] = 1;

				makeWall(cnt - 1,i,j);

				--aa; 
				++cc;
				board[i][j] = 0;
			}
		}
}
int main() {
	cin.tie(NULL);cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> n >> m;
	for (int i = 0;i < n;++i)
		for (int j = 0;j < m;++j) {
			cin >> board[i][j];
			if (board[i][j] == 1) ++aa; //aa는 벽
			if (board[i][j] == 2) ++bb; //bb는 초기 바이러스
			if (board[i][j] == 0) ++cc; //cc는 빈공간
		}
	
	makeWall(3,-1,-1);
	cout << ans;
	return 0;
}