結果

問題 No.13 囲みたい！
ユーザー monnu
提出日時 2021-07-13 22:58:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,213 bytes
コンパイル時間 1,732 ms
コンパイル使用メモリ 175,760 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 18:18:10
合計ジャッジ時間 2,523 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
#define MAX 1000000
#define MOD 1000000009
//#define MOD 998244353
//#define INF 1000000000
#define INF 1000000000000000000
int H,W;
int di[4]={1,0,-1,0};
int dj[4]={0,1,0,-1};
bool dfs(vector<vector<int>> &M,int i,int j,int pi,int pj,vector<vector<bool>> &visit){
  visit[i][j]=true;
  for(int k=0;k<4;k++){
    int ni=i+di[k];
    int nj=j+dj[k];
    if(ni<0||nj<0||ni>=H||nj>=W){
      continue;
    }
    if(ni==pi&&nj==pj){
      continue;
    }
    if(M[ni][nj]==M[i][j]){
      if(visit[ni][nj]==true){
        return true;
      }
      if(dfs(M,ni,nj,i,j,visit)){
        return true;
      }
    }
  }
  return false;
}

int main(){
  cin>>W>>H;
  vector<vector<int>> M(H,vector<int>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>M[i][j];
    }
  }
  vector<vector<bool>> visit(H,vector<bool>(W,false));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(visit[i][j]==false){
        if(dfs(M,i,j,-1,-1,visit)){
          cout<<"possible"<<endl;
          return 0;
        }
      }
    }
  }
  cout<<"impossible"<<endl;
}
0