結果

問題 No.13 囲みたい！
ユーザー imgry22imgry22
提出日時 2014-12-11 18:22:00
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,350 bytes
コンパイル時間 1,208 ms
コンパイル使用メモリ 165,184 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-11 20:35:45
合計ジャッジ時間 1,977 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int llu;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;

#define rrep(i, m, n) for(int i=m; i<n;  i++)
#define erep(i, n)    for(int i=1; i<=n; i++)
#define  rep(i, n)    for(int i=0; i<n;  i++)
#define rrev(i, m, n) for(int i=n-1; i>=m; i--)
#define erev(i, n)    for(int i=n; i>=1; i--)
#define  rev(i, n)    for(int i=n-1; i>=0; i--)
#define FOREACH(v)    (v).begin(), (v).end()
#define CNT(a, n, x)  (upper_bound(a, a+n, x)-lower_bound(a, a+n, x))
#define minup(m, x)   (m=min(m, x))
#define maxup(m, x)   (m=max(m, x))
#define mp            make_pair

#define INF 1000000000
#define MOD 1000000009
#define EPS 1E-8

void init(int n);
int find(int x);
void unite(int x, int y);
bool same(int x, int y);

#define MAX_W 100
#define MAX_H 100
#define MAX_N (MAX_W*MAX_H)

#define ok(i, j) (0<=(i)&&(i)<w && 0<=(j)&&(j)<h)

int w, h;
int m[MAX_W][MAX_H];
bool flag[MAX_W][MAX_H];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
queue<pair<pii, pii > > que;
pii start;
bool ok;
pii prev;

int main()
{
  cin >> h >> w;
  rep(i, w) rep(j, h) cin >> m[i][j];

  rep(i, w) rep(j, h) if(!flag[i][j]){
    start = mp(i, j);

    //    que.push(mp(mp(i, j), mp(i, j)));
    flag[i][j] = true;

    rep(k, 4) if(ok(i+dx[k], j+dy[k])) que.push(mp(mp(i+dx[k], j+dy[k]), mp(i, j)));

    while(!que.empty()){
      pii here = que.front().first;
      pii prev = que.front().second;
      int hx = here.first;
      int hy = here.second;
      que.pop();

      rep(k, 4) if(ok(hx+dx[k], hy+dy[k])){
        int nx = hx + dx[k];
        int ny = hy + dy[k];
        pii next = mp(nx, ny);

        if(next!=prev && (m[nx][ny]==m[i][j]) && flag[nx][ny]){
          printf("m=%d, %d\n", m[nx][ny], m[i][j]);
          printf("%d, %d\n", i, j);
          printf("%d, %d\n", hx, hy);
          printf("%d, %d\n", nx, ny);
          printf("%d, %d\n", prev.first, prev.second);
          puts("possible");
          return 0;
        }

        if(!flag[nx][ny] && m[i][j]==m[nx][ny]){
          que.push(mp(mp(nx, ny), mp(hx, hy)));
          flag[nx][ny] = true;
        }
      }
    }
  }

  puts("impossible");

  return 0;
}
0