NJPC2017: B - 格子グラフ
問題
解説
と仮定して、全体の本数を求めると
そこから使わない辺の数を引く。初めは簡単のために重複を許して引くことを考える。
- 角であれば 2
- 辺上であれば 3
- その他であれば 4
を引けば良い。しかしながら、引く辺のうちで重複がある。その重複した文をさらに足せば良い。 これらは与えられている個の頂点のうち任意の2ペアの頂点について、隣り合っているかどうかで判断ができる。
また、またはのときは条件が異なるため同様な方法で別処理に分ける。
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"; }