SRM 729 Med. FrogSquare

問題概要

n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。

誤解法

四隅だけ使えばよく,到達できるなら 3 手で行ける。

反例。4 手の例。四隅だけでは到達不可能。

解法

最初と最後以外は周上以外の点に移動する必要はない。周上の点の個数のオーダーは 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 手の例を作るのに手間取った。