結果

問題 No.157 2つの空洞
ユーザー TLwiegehttTLwiegehtt
提出日時 2015-07-13 03:40:22
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,055 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 26,480 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 14:50:01
合計ジャッジ時間 1,065 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,376 KB
testcase_01 AC 0 ms
4,380 KB
testcase_02 AC 0 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 0 ms
4,376 KB
testcase_05 AC 0 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 0 ms
4,380 KB
testcase_09 AC 0 ms
4,376 KB
testcase_10 AC 0 ms
4,376 KB
testcase_11 AC 0 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 0 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

char cave[25][25];

void printCave(int w, int h){
	int i,j;
	for(j=0;j<h;j++){
		for(i=0;i<w;i++){
			printf("%c", cave[j][i]);
		}
		printf("\n");
	}
}

void paintCave(int x, int y, char paint){
	int i;
	int px[] ={-1, 0, 1, 0};
	int py[] ={ 0,-1, 0, 1};
	
	if(cave[y][x] == '#'){
		return;
	}
	
	if(cave[y][x] == paint){
		return;
	}else{
		cave[y][x] = paint;
	}
	for(i=0;i<4;i++){
		paintCave(x+px[i], y+py[i], paint);
	}
	return;
}

int searchCave(int x, int y, int w, int h){
	int i,j;
	int tmp[25][25];
	int MOD = 200;
	int queue[230];
	int start, goal;
	
	for(j=0;j<h;j++){
		for(i=0;i<w;i++){
			tmp[j][i] = 999;
		}
	}
	
	tmp[y][x] = 0;
	start = goal = 0;
	queue[start] = (0*10000)+x*100+y;
	start = (start+1)%MOD;
	
	while(start != goal){
		int i;
		int qData = queue[goal];
		int qDis = qData/10000;
		int qx = (qData/100)%100;
		int qy = (qData%100);
		
		
		goal = (goal+1)%MOD;
		
		if( cave[qy][qx] == 'B' ){
			return qDis-1;
		}
		
		for(i=0;i<4;i++){
			int px[] ={-1, 0, 1, 0};
			int py[] ={ 0,-1, 0, 1};
			int tx = qx + px[i];
			int ty = qy + py[i];
			int tDis = qDis+1;
			if(tx <= 0){continue;}
			if(ty <= 0){continue;}
			if(tx >= (w-1)){continue;}
			if(ty >= (h-1)){continue;}
			if(cave[ty][tx] == 'A'){continue;}
			
			
			if(tDis < tmp[ty][tx]){
				tmp[ty][tx] = tDis;
				queue[start] = (tDis*10000) + (tx*100) + ty;
				start = (start+1)%MOD;
			}
		}
		
	}
	
	return 999999;
}

int main(void){
	int i,j;
	int w,h;
	int minDis = 20000;
	char paint = 'A';
	
	scanf("%d %d", &w, &h);
	
	for(j=0;j<h;j++){
		char str[25];
		scanf("%s", str);
		for(i=0;i<w;i++){
			cave[j][i] = str[i];
		}
	}
	
	
	for(j=0;j<h;j++){
		for(i=0;i<w;i++){
			if(cave[j][i] == '.'){
				paintCave(i,j,paint);
				if(paint == 'A'){
					paint = 'B';
				}else{
					paint = 'C';
				}
			}
		}
	}
	
	
//	printCave(w,h);
	
	for(j=0;j<h;j++){
		for(i=0;i<w;i++){
			if(cave[j][i] == 'A'){
				int ret = searchCave(i,j,w,h);
				if(ret < minDis){
					minDis = ret;
				}
			}
		}
	}
	
	printf("%d\n", minDis);
	
	return 0;
}
0