SRM 729 Med. FrogSquare
問題概要
n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。
誤解法
四隅だけ使えばよく,到達できるなら 3 手で行ける。
解法
最初と最後以外は周上以外の点に移動する必要はない。周上の点の個数のオーダーは O(n) なので,単純な BFS でも計算量は O(n2) となる。
class FrogSquare { public: int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) { vector<pair<int, int>> g; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == 0 || i == n - 1 || j == 0 || j == n - 1) { g.emplace_back(i, j); } } } g.emplace_back(tx, ty); queue<pair<int, int>> q; q.emplace(sx, sy); vector<vector<int>> dist(n, vector<int>(n, -1)); dist[sx][sy] = 0; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (auto p : g) { int xx = p.first; int yy = p.second; if ((xx - x) * (xx - x) + (yy - y) * (yy - y) >= d * d && dist[xx][yy] == -1) { dist[xx][yy] = dist[x][y] + 1; q.emplace(xx, yy); } } } return dist[tx][ty]; } };
図
\documentclass[margin=1cm]{standalone} \usepackage{tikz,newtxtext,newtxmath} \begin{document} \begin{tikzpicture}[ foo/.style={fill,circle,inner sep=0,minimum size=2mm}, ] \clip (-1,-1) rectangle (11,11); \draw [help lines] (0,0) grid (10,10); \node [foo] (z) at (8,8) {}; \node [foo] (a) at (0,0) {}; \node [foo] (b) at (10,5) {}; \node [foo] (c) at (0,10) {}; \node [foo] (d) at (8,2) {}; \draw (8,8) circle [radius=11cm]; \draw (0,0) circle [radius=11cm]; \draw (10,5) circle [radius=11cm]; \draw (0,10) circle [radius=11cm]; \draw [->,>=latex,thick] (z) -- (a); \draw [->,>=latex,thick] (a) -- (b); \draw [->,>=latex,thick] (b) -- (c); \draw [->,>=latex,thick] (c) -- (d); \end{tikzpicture} \end{document}
感想
自分の部屋では med の反例を作れる人がいなかったので,もし反例が作れてたらかなり稼げた(残念)。四隅の反例はすぐに作れたんだけど,4 手の例を作るのに手間取った。