SRM564 Div1 Easy

250

小さい場合はBFS。大きい場合は全て到達可能。
縦か横の長さが4以上だと全て到達可能になるらしい。

int bfs(int W, int H)
{
  bool vis[H][W];
  fill(&vis[0][0], &vis[H - 1][W - 1] + 1, false);
  vis[0][0] = true;
  queue< pair<int, int> > q;
  // (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), and (x-1,y-2)
  for (q.push(make_pair(0, 0)); q.size(); q.pop()) {
    pair<int, int> curr = q.front();
    const int D = 8;
    static const int di[D] = {+2, +2, -2, -2, +1, +1, -1, -1};
    static const int dj[D] = {+1, -1, +1, -1, +2, -2, +2, -2};
    for (int d = 0; d < D; ++d) {
      int ni = curr.first  + di[d];
      int nj = curr.second + dj[d];
      if (ni < 0 || nj < 0) continue;
      if (H <= ni || W <= nj) continue;
      if (vis[ni][nj]) continue;
      vis[ni][nj] = true;
      q.push(make_pair(ni, nj));
    }
  }
  return count(&vis[0][0], &vis[H - 1][W - 1] + 1, true);
}

class KnightCircuit2 {
public:
  int maxSize(int w, int h)
  {
    if (8 < h && 8 < w) return w * h;
    else return bfs(w, h);
  }
};