結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 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); | ^~~~~~~~~~~~~~~~
ソースコード
#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;}