結果

問題 No.13 囲みたい！
コンテスト
ユーザー akakimidori
提出日時 2017-04-19 15:29:02
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 327 ms / 5,000 ms
コード長 945 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 22,016 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 09:25:59
合計ジャッジ時間 1,167 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘run’:
main.c:32:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |   scanf("%d%d",&w,&h);
      |   ^~~~~~~~~~~~~~~~~~~
main.c:38:7: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |       scanf("%d",board+POS(i,j));
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

#define POS(i,j) ((i)*(w+2)+(j))

int dfs(int x,int y,int dir,int number,int *board,int w,int h){
  int dx[]={1,0,-1,0};
  int dy[]={0,1,0,-1};

  board[POS(x,y)]=-number;

  int k;
  for(k=0;k<4;k++){
    if(dir==k) continue;

    int nx=x+dx[k];
    int ny=y+dy[k];
    if(board[POS(nx,ny)]==-number){
      return 1;
    }
    if(board[POS(nx,ny)]==number){
      int t=dfs(nx,ny,(k+2)%4,number,board,w,h);
      if(t==1) return 1;
    }
  }
  return 0;
}

void run(void){

  int w,h;
  scanf("%d%d",&w,&h);

  int *board=(int *)calloc((w+2)*(h+2),sizeof(int));
  int i,j;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      scanf("%d",board+POS(i,j));
    }
  }

  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      int res=dfs(i,j,4,board[POS(i,j)],board,w,h);
      if(res==1){
	printf("possible\n");
	return;
      }
    }
  }
  printf("impossible\n");
  return;
}

int main(void){
  run();
  return 0;
}
0