Ito Campus
コンテスト中
考察
- イノシシがいる場所から距離Xまでを埋める。それからBFSすれば良さそう。
- でもこの解法はTLEになる
- 他にうまい方法が見つからず、迷走して終了。３０点は取れた
部分点コード
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1e8;;
int H, W, X;
char B[1111][1111];
int dist[1111][1111];
void Fill(int y, int x) {
struct P { int y, x; };
queue<P> que;
que.push({y, x});
B[y][x] = '#';
fill(dist[0], dist[1111], INF);
dist[y][x] = 0;
while (que.size()) {
P axis = que.front(); que.pop();
int y = axis.y, x = axis.x;
if (dist[y][x] >= X) return;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (B[ny][nx] != '.' || dist[ny][nx] != INF) continue;
B[ny][nx] = '#';
dist[ny][nx] = dist[y][x] + 1;
que.push({ny, nx});
}
}
}
int bfs(int sy, int sx, int gy, int gx) {
struct P { int y, x; };
queue<P> que;
que.push({sy, sx});
fill(dist[0], dist[1111], INF);
dist[sy][sx] = 0;
int ans = -1;
while (que.size()) {
P axis = que.front(); que.pop();
int y = axis.y, x = axis.x;
if (y == gy && x == gx) {
ans = dist[gy][gx];
break;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (B[ny][nx] != '.' || dist[ny][nx] != INF) continue;
dist[ny][nx] = dist[y][x] + 1;
que.push({ny, nx});
}
}
return ans;
}
signed main() {
// 入力。ついでに始点と終点を求める
cin >> H >> W >> X;
int sy, sx, gy, gx;
for (int yi = 0; yi < H; yi++) {
for (int xi = 0; xi < W; xi++) {
cin >> B[yi][xi];
if (B[yi][xi] == 'S') {
sy = yi, sx = xi;
B[yi][xi] = '.';
}
if (B[yi][xi] == 'G') {
gy = yi, gx = xi;
B[yi][xi] = '.';
}
}
}
// '@'を見つけたら、そこから距離Xを埋める
for (int yi = 0; yi < H; yi++) {
for (int xi = 0; xi < H; xi++) {
if (B[yi][xi] == '@') {
Fill(yi, xi);
}
}
}
// 通れる部分が判明している盤面ができてるので、あとはBFSするだけ
cout << bfs(sy, sx, gy, gx) << endl;
return 0;
}
問題点
- コードでいうと、以下の部分
// '@'を見つけたら、そこから距離Xを埋める
for (int yi = 0; yi < H; yi++) {
for (int xi = 0; xi < H; xi++) {
if (B[yi][xi] == '@') {
Fill(yi, xi);
}
}
-
@を探すループが$O(HW)$となる。 -
Fill()はBFSをする関数で計算量が$O(HW)$となる - よって全体の計算量が$O(H^2W^2)$になる
- $4 \leq H,W \leq 10^3$より、最大の計算ステップは$10^6 \times 10^6 = 10^{12}$になる。これでは間に合わない
改善策
無駄な部分を考えてみる
-
@を見つけたら、イノシシの移動可能範囲を塗りつぶす方法をとったらTLEした。 - この処理で無駄な部分は、何度も同じマスを塗りつぶすことである。
- 同じマスを何回も塗りつぶす必要はない。なので、直感的に考えると$O(HW)$でマスを埋める処理を個別にできそう
天才になる
- 天才になると、イノシシの移動範囲を並行的に埋めることができるのでは？という発想になる
いつもの経路探索BFSで考えようと思うと、以下の画像のようにイノシシの町からイノシシの初期位置に配置するとわかりやすい。
探索木にすると以下のようになる
実装でハマったところ
- このコードの60, 70行目。
if (ino[ny][nx] >= 0 && ino[ny][nx] <= X) continue; // これじゃないとだめ
// if (ino[ny][nx] <= X) continue; // これでもいい気がするんだけど、通らない
- コメントアウトしてる方の条件式を使うと、以下のケースで結果がおかしくなる
$ ./a.out
6 5 1
#####
#@#S#
#.#.#
#.#.#
#@#G#
#####
# イノシシ配列の埋まり方
-1 -1 -1 -1 -1
-1 0 -1 -1 -1
-1 1 -1 -1 -1
-1 1 -1 -1 -1
-1 0 -1 -1 -1
-1 -1 -1 -1 -1
- スタートからゴールまでが$-1$となっている。
if (ino[ny][nx] <= X)の条件式では$-1$がはじかれてしまう。
解決策1
-
if (ino[ny][nx] >= 0 && ino[ny][nx] <= X) continue;を使う。正しい条件式を書けば解決 - ただ、ハマった時これに気付くかは微妙なところ
-
if (hoge <= 5)みたいに片方サボってる条件式を見てあげる、みたいなデバッグをすれば良いのかもしれない
解決策2
- 配列の初期値を
INFにする - この配列は、なるべく小さい値が入る方が嬉しい。そういうときは初期値を
INFにするのが普通。
解法
- イノシシの場所を全てキューに突っ込む。そして、BFSをしてイノシシの移動範囲を配列で求める
- イノシシ配列を元にBFSして最短距離を求める
コード
#include <bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
const int INF = 1e8;
int H, W, X;
int sy, sx, gy, gx;
int ino[1111][1111];
int dist[1111][1111];
string B[1111];
// イノシシの移動範囲を埋める処理
void bfs1() {
struct P { int y, x; };
// データの初期化
fill(ino[0], ino[1111], INF);
// キューの初期化。イノシシの場所を全てキューに入れる
queue<P> que;
for (int yi = 0; yi < H; yi++) {
for (int xi = 0; xi < W; xi++) {
if (B[yi][xi] == '@') {
que.push({yi, xi});
ino[yi][xi] = 0;
B[yi][xi] = '#';
}
}
}
while (que.size()) {
P axis = que.front(); que.pop();
int y = axis.y, x = axis.x;
// 距離がX以上になったら終了
if (ino[y][x] >= X) break;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (B[ny][nx] == '#') continue;
if (ino[ny][nx] != INF) continue;
// データとキューを更新
B[ny][nx] = '#';
ino[ny][nx] = ino[y][x] + 1;
que.push({ny, nx});
}
}
}
// bfs1()で移動不可能な場所を'#'で埋めたため、bfs2()ではをいつものBFSやるだけ
int bfs2() {
struct P { int y, x; };
fill(dist[0], dist[1111], INF);
dist[sy][sx] = 0;
queue<P> que;
que.push({sy, sx});
int ans = -1;
while (que.size()) {
P axis = que.front(); que.pop();
int y = axis.y, x = axis.x;
if (y == gy && x == gx) {
ans = dist[y][x];
break;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (B[ny][nx] == '#') continue;
if (dist[ny][nx] != INF) continue;
dist[ny][nx] = dist[y][x] + 1;
que.push({ny, nx});
}
}
return ans;
}
signed main() {
// 入力。ついでに視点と終点の位置を変数に格納する
cin >> H >> W >> X;
for (int yi = 0; yi < H; yi++) {
cin >> B[yi];
for (int xi = 0; xi < W; xi++) {
if (B[yi][xi] == 'S') {
sy = yi, sx = xi;
B[yi][xi] = '.';
}
if (B[yi][xi] == 'G') {
gy = yi, gx = xi;
B[yi][xi] = '.';
}
}
}
// イノシシの移動範囲を埋める
bfs1();
// いつものBFSやるだけ
cout << bfs2() << endl;
return 0;
}
感想
- 並列で処理できるっていう発想、天才すぎないか。普通に思いつかないんだが
- 「各
@に関してBFSする」部分を「すべての@を一度に処理する」方法にしたら解けた。なるほどなーって感じ
参考にしたやつ
-
アルメリアさんの記事
- イノシシを同時並行で進める。一人で探索するBFSしかやったことないから、同時並行がイメージしづらかった。
- そこで、距離が０の点を確定させる→距離が１の点を確定させる→距離が２の点を確定させる→...みたいな感じで進めていくと考える
- すると、なるほどな〜ってなる
- いつも通り神のような記事でした。実装も参考にしました
-
はまやんさんのコード
- BFSを2回使うのが明示されててよかった（ありがとうございます）
- こうきさんとkakiraさんに教えてもらったやつ
- てんぷらさんのイノシシの町
おまけ
- なぜイノシシの位置の最小を取るのが最適なのかわからず迷走したやつ
- 難しく考えすぎた
本当に正しい？
- 僕はこの解法が直感的にわからないので、色々考えてみた
- 解法通りにマスを埋めていくと、画像右のような埋まり方になる。
- 各
@のみについてBFSすると、それぞれ画像中央のような埋まり方になる - 画像中央の３つの盤面の最小値をとったものが画像右の盤面になっていることがわかる
- 例えば画像中央の青文字の盤面を元に経路を探索することを考える。この時、$X=2$とする。すると、本来通れないマスも通れてしまうことがわかる。なので、小さい値を優先して埋めた方がいいことがなんとなーーーくわかる
数直線で考えてみる
- この問題ではイノシシの移動範囲を求めてから、その情報を元に経路探索をする
- 経路探索をする上で必要な情報は、あるマスの数値が「0以上X以下」であるか、「Xより大きい」かである
- この辺が割と重要な気がするけど、そこから先の考察が進まない...
- うーん、わからん。なんとなくわかるけど、なんかわからんくなった。
