[伯俊C+]2636チーズ

質問する

下図1に示すように、正方形の格子からなる正方形の板があり、その上に薄いチーズ(灰色の部分)が置かれています.板の縁(<図1>では、四角形のXの部分)にはチーズが入っておらず、チーズには1つ以上の穴が開いていてもよい.
これらのチーズを空気中に入れると溶け、空気に触れる車両は1時間後に溶けます.チーズの穴には空気が入っていませんが、穴を囲むチーズが溶けて穴が開くと空気が穴に入ります.<図1>に示すように、チーズ孔を囲むチーズは溶けず、図2>に示すように、「c」と表記された部分だけが1時間後に溶けて消える.
<図1>オリジナルチーズ形状
あと1時間で<図2>の「c」で表される部分は<図3>に示すように溶けて消えてしまいます.
<図2>1時間後のチーズの形
<図3>2時間後のチーズの形
<図3>チーズが2時間後の様子で、残りの破片はあと1時間で全部溶けてしまいました.そのため、初めてチーズが全部溶けて消えるまで3時間かかります.<図3>に示すように、チーズは融解中にいくつかに分けることができる.
矩形板の大きさとチーズが板に置かれたとき、空気中のチーズがすべて溶けるのに要する時間と、すべて溶ける1時間前にチーズの破片が残った格子数を入力するプログラムを作成します.

入力

最初の行は、矩形板の縦横長が正の整数であることを示します.縦横の長さは最大100です.板上の各横線の形状は、上から下へ順に2行目から最後の行までです.チーズのない格子は0で、チーズのある格子は1で、数字の間にスペースがあります.

しゅつりょく

1行目はチーズが全部溶けて消えるまでの時間を出力し、2行目は全部溶ける1時間前に置いたチーズの破片の格子数を出力します.
https://www.acmicpc.net/problem/2636

に答える

問題は親切です.地図の端が空いているので、特別な設備はなく、チーズのないどこでBFSをしても答えが得られます.
BFSにculocと、チーズの位置を保存するboo[]chezeを用意し、アクセス位置を記録するbool[]アクセスを準備します.
ナビゲーション時には,地図上を上下左右に移動するためにdx,dyを用意する.
ナビゲーション中にチーズが見つかった場合は、キューに入れずにチーズを削除します.
チーズが見つからない場合にのみ、その位置をキューに入れて探索を続けます.
正直、BFSの概念を熟知していれば、銀色の問題があります.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::queue; using std::pair;
typedef pair<int, int> pii;
/*
n,m : 맵크기
cheeze : 치즈위치 배열 true:치즈
visited : BFS에서 방문했는지 체크용
remainsCheeze = 방금전단계에서 남은 치즈
매단계마다 BFS 0,0부터 탐색, 탐색하며 치즈를 깎고, 탐색종료시
clear()실행
*/
int n, m, remainsCheeze=0, hour=1;
bool **cheeze, **visited; 
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

void clear();
void init();
int countCheeze();
void DEBUG();
void func();

void func() {
	queue<pii> loc;
	while (remainsCheeze > 0) { //치즈가 한개라도 남은경우
		loc.push({ 0,0 }); //0,0부터탐색
		visited[0][0] = true;

		while (!loc.empty()) {
			int x = loc.front().first; //현재위치 (x,y)
			int y = loc.front().second;
			loc.pop();

			//4방향으로탐색
			for (int d = 0; d < 4; d++) {
				int xx = x + dx[d]; //다음위치 (xx,yy)
				int yy = y + dy[d]; 

				//올바르지않은 범위
				if (xx < 0 || yy < 0 || xx == n || yy == m)
					continue;

				if (!visited[xx][yy]) {
					visited[xx][yy] = true;

					if (cheeze[xx][yy]) //치즈가있다면 없앰
						cheeze[xx][yy] = false; 
					else //치즈가 없다면 다음위치에서 탐색을 이어서 진행
						loc.push({ xx, yy }); 
				}
			}

		}

		//탐색후 모두 초기화
		clear();
		//DEBUG(); //디버그용

		if (countCheeze() == 0) //탐색후 치즈가 없는경우
			break;
		remainsCheeze = countCheeze();
		hour++;
	}
	printf("%d\n%d", hour, remainsCheeze);
}

void DEBUG() {
	printf("==================================%d 시간뒤\n", hour);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%2d", cheeze[i][j]);
		printf("\n");
	}
	printf("=====================================\n");
}

int countCheeze() { 
	int res = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (cheeze[i][j]) res++;
	return res;
}

void init() {
	scanf("%d%d", &n, &m);
	cheeze = new bool* [n];
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		cheeze[i] = new bool[m];
		visited[i] = new bool[m];
		for (int j = 0; j < m; j++) {
			scanf("%d", &cheeze[i][j]);
			visited[i][j] = false;
		}
	}
	remainsCheeze = countCheeze(); //남은치즈 초깃값
}

void clear() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visited[i][j] = false;
}

int main(void) {
	init();
	func();

	return 0;
}