結果

問題 No.13 囲みたい！
ユーザー mudbdb
提出日時 2015-06-24 22:11:24
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 129 ms / 5,000 ms
コード長 1,921 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 22,272 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 10:44:31
合計ジャッジ時間 1,335 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:56:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |   scanf("%d", &W);
      |   ^~~~~~~~~~~~~~~
main.c:57:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |   scanf("%d", &H);
      |   ^~~~~~~~~~~~~~~
main.c:61:7: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |       scanf("%d", &(M[i+W*j]));
      |       ^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
int W = 0;
int H = 0;
int *M = 0;
int Target = -1;
char *Move = 0;
int *Path = 0;
int Shift = 8;
int move(int i, int j, int move_no)
{
  int rc = 0;
  if ((0<=i) && (i<W) && (0<=j) && (j<H)) {
    if (M[i+W*j]==Target) {
      if (move_no >= 2) {
        if (Path[move_no-2] == ((i << Shift) | j)) {
          rc = 0;
          goto END;
        } else {
          Path[move_no] = (i << Shift) | j;
        }
      } else {
        Path[move_no] = (i << Shift) | j;
      }
    } else {
      rc = 0;
      goto END;
    }
  } else {
    rc = 0;
    goto END;
  }
  if (Move[i+W*j] == 1) {
    rc = 1;
  } else {
    Move[i+W*j] = 1;
    if (1 == move(i+1, j, move_no+1)) {
      rc = 1;
    } else if (1 == move(i, j+1, move_no+1)) {
      rc = 1;
    } else if (1 == move(i-1, j, move_no+1)) {
      rc = 1;
    } else if (1 == move(i, j-1, move_no+1)) {
      rc = 1;
    } else {
      rc = 0;
    }
  }
END:
  ;
  return rc;
}
int main()
{
  int i, j;
  scanf("%d", &W);
  scanf("%d", &H);
  M = (int*)malloc(sizeof(int)*W*H);
  for (j=0; j<H; j++) {
    for (i=0; i<W; i++) {
      scanf("%d", &(M[i+W*j]));
    }
  }

  char *ans = "impossible";
  char *visit;
  Move = (char*)malloc(sizeof(char)*W*H);
  visit = (char*)malloc(sizeof(char)*W*H);
  Path = (int*)malloc(sizeof(int)*W*H);
  for (j=0; j<H; j++) {
    for (i=0; i<W; i++) {
      Move[i+W*j] = 0;
      visit[i+W*j] = 0;
    }
  }
  for (j=0; j<H; j++) {
    for (i=0; i<W; i++) {
      if (visit[i+W*j] == 0) {
        Target = M[i+W*j];
        if (1 == move(i, j, 0)) {
          ans = "possible";
          goto END;
        } else {
          int ii, jj;
          for (jj=0; jj<H; jj++) {
            for (ii=0; ii<W; ii++) {
              visit[ii+W*jj] |= Move[ii+W*jj];
              Move[ii+W*jj] = 0;
            }
          }
        }
      }
    }
  }

END:
  ;
  printf("%s\n", ans);
  return 0;
}
0