yukicoder No.13 囲みたい！

問題

問題概要

閉路検出

解法

考え方が悪かった。閉路検出のためにある始点から初めて、1周してその点に戻るかを判別すればいいなと思い、dfsもどきのbfsみたいなのを書き出したが完全に悪かった。閉路検出は「ある始点からスタートして、探索方向はfrom以外の方向に進み、一度探索した場所(スタート時点でなくてもいい)に戻れれば良い」という考えを持てばよかった。何も、スタート時点に戻れるかで判別する必要はなく、すでに訪れたところに行ければ閉路はできている。 実装はbfsもdfsも来た方に戻らないようにすることと、一度探索した部分に戻ることができることができれば、閉路があったことになるということに気をつけてやればいい。

ミス

下記のような1方向だけに進むように書いたbfsでwaしまくった。dfsなら深く突き進んだ後進めなければ、戻ってくることができるけれど、以下の実装だと、それができていないので、テストケースが1つ通らないのだと思う。スタートにもどれれば良いとい考えで書いたコードがMLE。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int w, h;
int b[110][110];
int used[110][110];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
int main(void){
    cin >> w >> h;
    rep(i, h)rep(j, w) cin >> b[i][j];
    rep(i, h)rep(j, w) used[i][j] = 0;

    rep(i, h)rep(j, w){
        // printf("%d %d\n", i, j);
        rep(a, h)rep(b, w)used[a][b] = 0;
        queue<pair<int, int> > q;
        int num = b[i][j];
        used[i][j] = 1;//逆戻りを防ぐように
        q.push(make_pair(i, j));
        while(!q.empty()){
            auto now = q.front(); q.pop();
            rep(k, 4){
                int y = now.first + dy[k], x = now.second + dx[k];
                if(y < 0 || h <= y || x < 0 || w <= x) continue;
                if(y == i && x == j && used[now.first][now.second] >= 4){
                    printf("possible\n");
                    return 0;
                }
                if(b[y][x] == num && used[y][x] == 0){
                    q.push(make_pair(y, x));
                    used[y][x] = used[now.first][now.second] + 1;
                    break;
                }

            }
        }
    }
    printf("impossible\n");
    return 0;
}

コード

bfs

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int w, h;
int b[110][110];
bool d[110][110];//一度調べた部分を記録
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main(void){
    cin >> w >> h;
    rep(i, h)rep(j, w) cin >> b[i][j];
    rep(i, 110)rep(j, 110) d[i][j] = false;
    rep(i, h)rep(j, w){
        if(d[i][j]) continue;//すでに調べている
        int used[110][110];//今回の記録用
        rep(a, 110)rep(b, 110)used[a][b] = 0;
        queue<pair<int, int> > q;
        queue<int> v;
        int num = b[i][j];
        used[i][j] = 1; d[i][j] = true;
        q.push(make_pair(i, j));//スタート
        v.push(-1);
        while(!q.empty()){
            auto now = q.front(); q.pop();
            auto from = v.front(); v.pop();
            rep(k, 4){
                if(from == (k + 2) % 4 && from != -1) continue;//来た方向に戻るのを防ぐ
                int y = now.first + dy[k], x = now.second + dx[k];
                if(y < 0 || h <= y || x < 0 || w <= x) continue;
                if(used[y][x] == 1){
                    printf("possible\n");
                    return 0;
                }
                if(b[y][x] == num && used[y][x] == 0){
                    q.push(make_pair(y, x));
                    v.push(k);
                    used[y][x] = 1; d[i][j] = true;
                }

            }
        }
        
    }
    printf("impossible\n");
    return 0;
}

dfs

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int w, h;
int b[110][110];
bool d[110][110];//一度調べた部分を記録
int used[110][110];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool flag = false;

void bfs(int y, int x, int py, int px, int num){
    d[y][x] = true; used[y][x] = 1;
    rep(i, 4){
        int nowy = y + dy[i], nowx = x + dx[i];
        if(nowy < 0 || h <= nowy || nowx < 0 || w <= nowx) continue;
        if(nowy == py && nowx == px) continue;//戻るの禁止
        if(b[nowy][nowx] != num) continue;
        if(used[nowy][nowx]){
            flag = true;
            return;
        }
        bfs(nowy, nowx, y, x, num);
    }
    return;
}

int main(void){
    cin >> w >> h;
    rep(i, h)rep(j, w) cin >> b[i][j];
    rep(i, h)rep(j, w){
        if(d[i][j]) continue;
        rep(a, 110)rep(b, 110) used[a][b] = 0;
        bfs(i, j, -1, -1, b[i][j]);
    }
    if(flag) printf("possible\n");
    else printf("impossible\n");
    return 0;
}