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; }