結果

問題 No.13 囲みたい！
コンテスト
ユーザー siman
提出日時 2016-03-29 06:20:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 691 ms / 5,000 ms
コード長 1,657 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 73,756 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 10:50:42
合計ジャッジ時間 1,952 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits.h>
#include <time.h>
#include <string>
#include <string.h>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

const int DY[4] = {-1, 0, 0, 1};
const int DX[4] = { 0,-1, 1, 0};

const int MAX_H = 100;
const int MAX_W = 100;

struct Coord {
  int y;
  int x;
  int dist;

  Coord(int y = -1, int x = -1, int dist = -1){
    this->y = y;
    this->x = x;
    this->dist = dist;
  }
};

int w, h;
int field[MAX_H][MAX_W];
int oy, ox;
int checkCount;
bool success;
int checkField[MAX_H][MAX_W];

void dfs(int y, int x, int dist, int num){
  if(success) return;
  if(field[y][x] != num) return;

  if(y == oy && x == ox && dist >= 4){
    success = true;
    return;
  }
  if(checkField[y][x] == checkCount) return;
  checkField[y][x] = checkCount;

  for(int i = 0; i < 4; i++){
    int ny = y + DY[i];
    int nx = x + DX[i];

    if(ny < 0 || h <= ny || nx < 0 || w <= nx) continue;
    dfs(ny, nx, dist+1, num);
  }
}

int main(){
  cin >> w >> h;

  memset(field, -1, sizeof(field));
  memset(checkField, -1, sizeof(checkField));
  success = false;
  checkCount = 0;

  for(int y = 0; y < h; y++){
    for(int x = 0; x < w; x++){
      cin >> field[y][x];
    }
  }

  for(int y = 0; y < h; y++){
    for(int x = 0; x < w; x++){
      int num = field[y][x];
      oy = y;
      ox = x;

      checkCount++;
      dfs(y, x, 0, num);
    }
  }

  if(success){
    cout << "possible" << endl;
  }else{
    cout << "impossible" << endl;
  }
  return 0;
}
0