結果

問題 No.157 2つの空洞
コンテスト
ユーザー TLwiegehtt
提出日時 2015-07-13 03:40:22
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,055 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 22,656 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 06:23:55
合計ジャッジ時間 1,039 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:98:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |         scanf("%d %d", &w, &h);
      |         ^~~~~~~~~~~~~~~~~~~~~~
main.c:102:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |                 scanf("%s", str);
      |                 ^~~~~~~~~~~~~~~~

ソースコード

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