글 읽기 - 반례좀 부탁드립니다..ㅠㅠㅠ

cool2684 5년 전 0

ㅈㅔ가 해본 예제들은 다 되는데 반례좀 부탁드려용

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int n, m;
int map[51][51];
bool check[51][51];
bool check2[51][51];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int max_ = 0;
int space = 0;
int wall_break_max = 0;

int DtoB(int x) {
	int sum = 0;
	int i = 1000;
	while (x!=0) {
		sum += (x % 2)*i;
		x = x / 2;
		i /= 10;
	}
	return sum;
}

void bfs(int y, int x) {
	if (check[y][x] == true)
		return;

	space++;

	int cnt = 1;
	check[y][x] = true;
	queue<tuple<int, int, int>> q;
	q.push(make_tuple(y, x, 0));

	while (!q.empty()) {
		y = get<0>(q.front());
		x = get<1>(q.front());
		int wall = get<2>(q.front());
		q.pop();

		int j = 0;
		int temp = map[y][x];
		for (int i = 1; i <= 1000; i *= 10) {
			if (temp % 10 * i == 0 && check[y + dy[j]][x + dx[j]] != true
				&& y + dy[j] >= 0 && y + dy[j] < m && x + dx[j] >= 0 && x + dx[j] < n) {
				check[y + dy[j]][x + dx[j]] = true;
				q.push(make_tuple(y + dy[j], x + dx[j], wall));
				cnt++;
			}
			temp = temp / 10;
			++j;
		}
	}

	if (max_ < cnt) {
		max_ = cnt;
	}
}

void bfs2(int y, int x) {
	if (check2[y][x] == true)
		return;

	int wall_break_cnt = 1;
	check2[y][x] = true;
	queue<tuple<int, int, int>> q;
	q.push(make_tuple(y, x, 0));

	while (!q.empty()) {
		y = get<0>(q.front());
		x = get<1>(q.front());
		int wall = get<2>(q.front());
		q.pop();

		int j = 0;
		int temp = map[y][x];
		for (int i = 1; i <= 1000; i *= 10) {
			if (temp % 10 * i == 0 && check2[y + dy[j]][x + dx[j]] != true
				&& y + dy[j] >= 0 && y + dy[j] < m && x + dx[j] >= 0 && x + dx[j] < n) {
				check2[y + dy[j]][x + dx[j]] = true;
				q.push(make_tuple(y + dy[j], x + dx[j], wall));
				wall_break_cnt++;
			}
			temp = temp / 10;
			++j;
		}

		j = 0;
		temp = map[y][x];
		for (int i = 1; i <= 1000; i *= 10) {
			if (temp % 10 * i == 1 && check2[y + dy[j]][x + dx[j]] != true && wall == 0
				&& y + dy[j] >= 0 && y + dy[j] < m && x + dx[j] >= 0 && x + dx[j] < n) {
				check2[y + dy[j]][x + dx[j]] = true;
				q.push(make_tuple(y + dy[j], x + dx[j], wall + 1));
				wall_break_cnt++;
			}
			temp = temp / 10;
			++j;
		}

	}

	if (wall_break_max < wall_break_cnt) {
		wall_break_max = wall_break_cnt;
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			int x;
			cin >> x;
			map[i][j] = DtoB(x);
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			bfs(i, j);
			bfs2(i, j);
		}
	}

	cout << space << endl <<max_ <<endl << wall_break_max;

	return 0;
}

akaishuichi 5년 전 2

4 1

15 15 15 15

이렇게 하면

정답이 4

가 나와야 하는데

1이 나옵니다.

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

문제

문제

출처

ICPC

반례좀 부탁드립니다..ㅠㅠㅠ

cool2684 5년 전 0

akaishuichi 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말