結果

問題 No.13 囲みたい！
ユーザー itezpaceitezpace
提出日時 2016-09-01 12:10:19
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,436 bytes
コンパイル時間 1,276 ms
コンパイル使用メモリ 73,704 KB
実行使用メモリ 177,568 KB
最終ジャッジ日時 2024-11-15 16:35:04
合計ジャッジ時間 13,808 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
177,568 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 TLE -
testcase_04 AC 3 ms
5,248 KB
testcase_05 TLE -
testcase_06 AC 90 ms
5,248 KB
testcase_07 WA -
testcase_08 AC 33 ms
5,248 KB
testcase_09 WA -
testcase_10 AC 6 ms
5,248 KB
testcase_11 AC 25 ms
5,248 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 11 ms
5,248 KB
testcase_14 AC 11 ms
5,248 KB
testcase_15 AC 2 ms
13,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int w,h,m;
int ary[100][100];
int mx[3]={1,-1,0};
int my[3]={0,0,-1};

int calc(int i,int j,int o,int tj,int ts,int te,vector<vector<int>> vv){
  int i2=i;
  int ret=0;
  for(int i=0; i<3; ++i){
    int px=o+mx[i];
    int py=j+my[i];
    if(0<=px && px<w && 0<=py && py<h && ary[py][px]==i2){
      if(py==tj && ts<=px && px>=te){
        ret=1;
      } else {
        vector<vector<int>> vv2=vv;
        if(vv2[py][px]==0){
          vv2[py][px]=1;
          ret+=calc(i2,py,px,tj,ts,te,vv2);
        }
      }
    }
  }
  return ret;
}

int main(){
  cin>>w>>h;
  int n=0;
  for(int i=0; i<h; ++i){
    for(int j=0; j<w; ++j){
      cin>>m;
      ary[i][j]=m;
      if(n<m) n=m;
    }
  }
  for(int i=1; i<=n; ++i){
    vector<tuple<int,int,int>> v;
    for(int j=0; j<h; ++j){
      int f=0;
      int s=101;
      int e=101;
      for(int k=0; k<w-1; ++k){
        int a=ary[j][k];
        if(a==i){
        int b=ary[j][k+1];
        if(f==0){
          if(a==b){
            s=k;
            f=1;
          }
        } else {
          if(a!=b || (a==b && k==w-2)){
            e=k;
            if(a==b && k==w-2) e=k+1;
            f=0;
            tuple<int,int,int> t=make_tuple(j,s,e);
            v.push_back(t);
            for(int l=0; l<v.size(); ++l){
              int& tj=get<0>(v[l]);
              int& ts=get<1>(v[l]);
              int& te=get<2>(v[l]);
              if(tj<j){
                int x=0;
                for(int o=s; o<=e; ++o){
                  if(ary[j-1][o]==i){
                    if(o<e && ary[j-1][o+1]==i){
                      cout<<"possible"<<endl;
                      return 0;
                    } else {
                      vector<vector<int>> vv;
                      vv.resize(h);
                      for(int i2=0;i2<h;++i2){
                        vv[i2].resize(w);
                        for(int j2=0;j2<w;++j2){
                          vv[i2][j2]=0;
                        }
                      }
                      int y=calc(i,j-1,o,tj,ts,te,vv);
                      if(y>0) x+=1;
                    }
                  }
                }
                if(x>=2) {
                  cout<<"possible"<<endl;
                  return 0;
                }
              }
            } 
          }
        }
        }
      }
    }
  }
  cout<<"impossible"<<endl;
  return 0;
}
0