글 읽기 - 사람 한명 살려주세요

gusdnr9875 2년 전 0

3일 짼데 도저히 반례가 안보입니다. 심지어 코드 돌리면 바로 틀렸습니다. 라고 뜨는데,,

반례하나만 찾아주시면 너무 감사하겠습니다.. ㅠㅠㅠ

정말 약소하지만 반례찾아주시면 커피 기프티콘이라도 보내드리겠습니다. ㅠㅠ

부탁드립니다. 선생님들

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
int arr[1001][1001] = { 0, };
vector <pair<int, int>> block;
int result[1001][1001] = { 0, };

int visited[1001][1001][2] = { 0, }; // 첨에는 이동 가능한 개수를 저장할거고, 두번째에는 고유 영역 값을 저장할 예정
int vis_cnt = 1; // 구획의 첫 번호는 1부터 

bool temp_v[1001][1001] = { 0, }; //난 bfs로 구현할거야, 얘는 탐색을 위해 사용할 배열

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };


void bfs(int ty, int tx) {

	// 1. temp_v를 사용해서 이동 가능한 개수 파악하기
	int maxed = 1;
	temp_v[ty][tx] = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (temp_v[ny][nx] != 0)
				continue;
			temp_v[ny][nx] = 1;
			que.push(make_pair(ny, nx));
			maxed++;
		}
	}
	//cout << maxed << endl;

	// 2. visited에 이동가능한 개수와 자신의 구획번호를 입력하기 
	visited[ty][tx][0] = maxed;
	visited[ty][tx][1] = vis_cnt;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (visited[ny][nx][0] != 0)
				continue;
			visited[ny][nx][0] = maxed;
			visited[ny][nx][1] = vis_cnt;
			que.push(make_pair(ny, nx));
		}
	}



	vis_cnt++; //인덱스를 하나 올려준다.


}

int main() {
	ios_base::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 1)
				block.push_back(make_pair(i, j));
		}
	}

	//cout << block.size() << endl;

	//1. 영역별로 마킹하기!

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp_v[i][j] == 0 && arr[i][j] == 0) { // 벽이 아니고, 방문한 적이 없다면 탐색해야해!
				bfs(i, j);
			}

	/*
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++)
	cout << visited[i][j][] << ' ';
	cout << endl;
	}
	*/

	//2. 벽을 하나씩 부수면서 이동가능한 결과값을 도출하는 과정 

	vector <int> index; // index 값들을 임시 저장할 친구 
	for (int i = 0; i < block.size(); i++) {
		index.clear();
		int val = 1; //자신을 포함해야 하니 1 부터 시작한다. 
		bool flag = true;
		int y = block[i].first;
		int x = block[i].second;

		for (int j = 0; j < 4; j++) {
			int ny = y + y_ar[j];
			int nx = x + x_ar[j];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 1)
				continue;
			for (int i = 0; i < index.size(); i++)
				if (visited[ny][nx][1] == index[i]) {
					flag = false;
					break;
				}
			if (flag == true) {
				val += visited[ny][nx][0];
				index.push_back(visited[ny][nx][1]);
			}
		}

		result[y][x] = val % 10;
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d", result[i][j]);
		printf("\n");
	}

}

bamgoesn 2년 전 1

반례입니다. 기프티콘은 안 주셔도 됩니다.

gusdnr9875 2년 전 0

어 너무 감사합니다. ㅠㅠㅠ

맘바뀌시면 언제든지 이메일 남겨주세요! ㅎㅎ
너무너무 감사합니다

kimhot6 1년 전 0

덕분에 풀었습니다 감사합니다

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

문제

문제

출처

ICPC

사람 한명 살려주세요

gusdnr9875 2년 전 0

bamgoesn 2년 전 1

gusdnr9875 2년 전 0

kimhot6 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말