글 읽기 - 반례가 어떻게 될까요...

luckystay 3년 전 0

아무리 해도 못찾겠습니다 ㅠㅠ. 고수님들 답변 기다리겠습니다!

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int row, col;
int **mat;
int **che;
int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
int maxx = -1;

void bfs(queue <pair<int, int> > que) {
	pair <int, int> now;
	int nx, ny, cou = 0;
	
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			che[i][j] = mat[i][j];
	while (!que.empty()) {
		now = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			nx = now.first + dir[i][0];
			ny = now.second + dir[i][1];
		
			if (nx >= 0 && nx < row&& ny >= 0 && ny < col && che[nx][ny] == 0) {
				che[nx][ny] = 1;
				que.push(make_pair(nx, ny));
			}
		}
	}
	for (int i = 0; i < row; i++)
		for (int j = 0; j < row; j++)
			if (che[i][j] == 0)
				cou++;
	if (cou > maxx) maxx = cou;
}

int main(void) {
	queue <pair<int, int> > que;
	scanf("%d %d", &row, &col);
	mat = new int*[row];
	che = new int*[row];
	for (int i = 0; i < row; i++)
		che[i] = new int[col];
	for (int i = 0; i < row; i++)
		mat[i] = new int[col];

	for(int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			scanf("%d", &mat[i][j]);
			if (mat[i][j] == 2)
				que.push(make_pair(i, j));
		}

	for (int i = 0; i < row*col; i++) {
		if (mat[i / col][i % col] == 1 || mat[i / col][i%col] == 2) continue;
		else mat[i / col][i % col] = 1;
		for (int j = i; j < row*col; j++) {
			if (mat[j / col][j % col] == 1 || mat[j / col][j%col] == 2) continue;
			else mat[j / col][j % col] = 1;
			for (int k = j; k < row*col; k++) {
				if (mat[k / col][k%col] == 1 || mat[k / col][k%col] == 2) continue;
				else {
					mat[k / col][k % col] = 1;
					bfs(que);
					mat[k / col][k % col] = 0;
				}
			}
			mat[j / col][j % col] = 0;
		}
		mat[i / col][i % col] = 0;
	}
	printf("%d", maxx);
	for (int i = 0; i < row; i++)
		delete[] mat[i];
	delete[] mat;
	for (int i = 0; i < row; i++)
		delete[] che[i];
	delete[] che;
	return 0;
}

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

문제

문제

출처

ICPC

반례가 어떻게 될까요...

luckystay 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말