結果

問題 No.157 2つの空洞
コンテスト
ユーザー asugen0402
提出日時 2018-12-27 15:26:17
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 3,793 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 32,000 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 14:52:08
合計ジャッジ時間 817 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_SIZE_MAX		20										// 最大サイズ
#define D_MASS_EMPTY	'.'										// マス - 空洞
#define D_MASS_WALL		'#'										// マス - 壁

// 内部変数
static FILE *szpFpI;											// 入力
static int siW, siH;											// 幅・高さ
static char sc2Mass[D_SIZE_MAX][D_SIZE_MAX + 5];				// マス

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
#endif

// 空洞 - 取得
int
fGetEmpty(
	int *pipX					// <O> 位置X
	, int *pipY					// <O> 位置Y
)
{
	int i, j;

	for (i = 0; i < siH; i++) {
		for (j = 0; j < siW; j++) {
			if (sc2Mass[i][j] == D_MASS_EMPTY) {
				*pipX = j;
				*pipY = i;
				return 0;
			}
		}
	}

	return -1;
}

// 空洞 - クリア
int
fClearEmpty(
	int piX						// <I> 位置X
	, int piY					// <I> 位置Y
)
{
	// 範囲外チェック
	if (piX < 0 || siW <= piX) {
		return -1;
	}
	if (piY < 0 || siH <= piY) {
		return -1;
	}

	// 空洞かチェック
	if (sc2Mass[piY][piX] != D_MASS_EMPTY) {
		return -1;
	}

	// クリア
	sc2Mass[piY][piX] = 0;

	// 上下左右へ
	fClearEmpty(piX + 1, piY);
	fClearEmpty(piX - 1, piY);
	fClearEmpty(piX, piY + 1);
	fClearEmpty(piX, piY - 1);

	return 0;
}

// 壁 - 空洞化
int
fChgWall(
	int piX						// <I> 位置X
	, int piY					// <I> 位置Y
	, int piENo					// <I> 対象の空洞
)
{
	// 範囲外チェック
	if (piX < 0 || siW <= piX) {
		return 0;
	}
	if (piY < 0 || siH <= piY) {
		return 0;
	}

	// もう１つの空洞かチェック
	if (sc2Mass[piY][piX] == D_MASS_EMPTY) {
		return 1;
	}

	// 壁かチェック
	if (sc2Mass[piY][piX] != D_MASS_WALL) {
		return 0;
	}

	// 空洞化
	sc2Mass[piY][piX] = piENo;

	return 0;
}

// 空洞 - 拡大
int
fWideEmpty(
	int piENo					// <I> 対象の空洞
)
{
	int i, j;

	for (i = 0; i < siH; i++) {
		for (j = 0; j < siW; j++) {
			if (sc2Mass[i][j] == piENo) {

				// 上下左右の壁
				int liRet = fChgWall(j + 1, i, piENo + 1);
				liRet += fChgWall(j - 1, i, piENo + 1);
				liRet += fChgWall(j, i + 1, piENo + 1);
				liRet += fChgWall(j, i - 1, piENo + 1);
				if (liRet != 0) {							// 連結
					return 1;
				}
			}
		}
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 幅・高さ - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siW, &siH);

	// マス - 取得
	for (i = 0; i < siH; i++) {
		fgets(sc2Mass[i], sizeof(sc2Mass[i]), szpFpI);
	}

	// 空洞 - 取得
	int liX, liY;
	fGetEmpty(&liX, &liY);

	// 空洞 - クリア
	fClearEmpty(liX, liY);

	// 空洞 - 拡大
	for (i = 0; ; i++) {
		int liRet = fWideEmpty(i);
		if (liRet != 0) {
			break;
		}
	}

	// 結果 - セット
	sprintf(lc1Out, "%d\n", i);

	// 結果 - 表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}
0