NJPC2017: B - 格子グラフ

問題

B - 格子グラフ

解説

N = 0と仮定して、全体の本数を求めるとH * (W - 1) + W * (H - 1)

そこから使わない辺の数を引く。初めは簡単のために重複を許して引くことを考える。

  • 角であれば 2
  • 辺上であれば 3
  • その他であれば 4

を引けば良い。しかしながら、引く辺のうちで重複がある。その重複した文をさらに足せば良い。 これらは与えられているN個の頂点のうち任意の2ペアの頂点について、隣り合っているかどうかで判断ができる。

また、H = 1またはW = 1のときは条件が異なるため同様な方法で別処理に分ける。

int N;

bool adjacent(P a, P b) {
  auto w = abs(a.first - b.first);
  auto h = abs(a.second - b.second);
  return w + h == 1;
}

void solve1(int H, int W, vector<P> const& vs) {
  int nouse = 0;
  rep(i, N) {
    vector<P> ones = {
      P{1, W}, P{H, 1},
    };
    for (auto e: ones) if (vs[i] == e) {
      nouse++;
      goto next;
    }    
    nouse += 2;
  next:;
  }
  int restored = 0;
  rep(i, vs.size()) REP(j, i + 1, vs.size()) {
    restored += adjacent(vs[i], vs[j]);
  }
  cout << max((int64_t)0, (int64_t)H * W - 1 - nouse + restored) << "\n";
}

int main() {
  int H, W; cin >> H >> W >> N;

  if (H == 1 || W == 1) {
    vector<P> vs(N); cin >> vs;
    solve1(H, W, vs);
    return 0;
  }

  vector<P> vs;
  int nouse = 0;
  rep(i, N) {
    int r, c; cin >> r >> c;
    vs.emplace_back(r, c);
    if ((r == 1 && c == 1) ||
        (r == 1 && c == W) ||
        (r == H && c == 1) ||
        (r == H && c == W)) {
      nouse += 2;
    }
    else if (r == 1 || c == 1 || r == H || c == W) {
      nouse += 3;
    }
    else {
      nouse += 4;
    }
  }
  int restored = 0;
  rep(i, vs.size()) REP(j, i + 1, vs.size()) {
    if (adjacent(vs[i], vs[j])) {
      restored++;
    }
  }
  cout << max(0LL, (2LL * H * W - (H + W) - nouse + restored)) << "\n";
}