글 읽기 - 반례를 알 수 있을까요?

kth 5년 전 0

시간초과면 이해가 가겠는데 틀렸습니다 뜨는 이유를 모르겠습니다. 예외케이스가 있을까요?

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

using namespace std;

int n, m, result, tmp_res, map[8][8], visited[8][8], copy_map[8][8];
vector<pair<int, int>> virus;

void dfs(int row_start, int col_start, int selected, int max);
void bfs(int row, int col);
int is_limit(int row, int col);

int main(void) {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) 
				virus.push_back(make_pair(i, j));
		}
	}
	dfs(0, 0, 0, 3);
	printf("%d\n", result);
}

void dfs(int row_start, int col_start, int selected, int max) {//3개 벽 영역 선택
	if (selected >= max) {
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++) {
				visited[i][j] = 0;
				copy_map[i][j] = map[i][j];
			}
		}
		tmp_res = 0;
		for (int i = 0; i < virus.size(); i++) {//바이러스 확산
			if(visited[virus[i].first][virus[i].second] == 0)
				bfs(virus[i].first, virus[i].second);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0)
					tmp_res++;
			}
		}
		if (tmp_res > result) {
			result = tmp_res;
			/*바이러스 확산 확인용
			printf("\n");
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					printf("%d ", map[i][j]);
				}
				printf("\n");
			}
			printf("\n");
			*/
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = copy_map[i][j];
			}
		}
		return;
	}
	for (int i = row_start; i <= row_start; i++) {//한 행 돌기
		for (int j = col_start + 1; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				dfs(i, j, selected + 1, max);
				map[i][j] = 0;
			}
		}
	}
	for (int i = row_start + 1; i < n; i++) {//다음 행 부터 돌기
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				dfs(i, j, selected + 1, max);
				map[i][j] = 0;
			}
		}
	}
}

void bfs(int row, int col) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));
	visited[row][col] = 1;
	int dx[] = { -1, 1, 0, 0 };
	int dy[] = { 0, 0, -1, 1 };
	while (!q.empty()) {
		int here_row = q.front().first;
		int here_col = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int there_row = here_row + dx[i];
			int there_col = here_col + dy[i];
			if (!is_limit(there_row, there_col) && map[there_row][there_col] == 0 && visited[there_row][there_col] == 0) {
				map[there_row][there_col] = 2;
				visited[there_row][there_col] = 1;
				q.push(make_pair(there_row, there_col));
			}
		}
	}
}

int is_limit(int row, int col) {
	if (row < 0 || row >= n || col < 0 || col >= m)
		return 1;
	return 0;
}

djm03178 5년 전 0

문제 번호 적는 칸에 문제 번호를 적어주세요.

jung2381187 5년 전 0

14502번이네요

djm03178 5년 전 4

23번째 줄은 과연 (0, 0)칸부터 벽을 놓는 경우를 고려할까요?

3 3

0 0 0

2 1 0

1 1 1

kth 5년 전 0

맨 처음 선택한 벽을 검사안했군요. 정말 감사합니다.ㅎㅎ

for (int i = row_start; i <= row_start; i++)
    for (int j = col_start + 1; j < m; j++) { // 이부분이 문제였네요. j = col_start로 바꿔주니 잘 되네염 ㅎ

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

kth 5년 전 0

djm03178 5년 전 0

jung2381187 5년 전 0

djm03178 5년 전 4

kth 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말