ARC 061 D - すぬけ君の塗り絵 / Snuke's Coloring
問題概要
HxWの2次元マスの中で考えられる3x3のマスを考え、それぞれの3x3のマスの中に黒のマスがいくつあるかを調べる。
解法
HxWのマスを持つことはできない。また制約を見ると、ほとんどの部分が白のマスであり、黒の部分は少数である。よって、与えられる黒のマスの周りの3x3のマスのみ調べれば、3x3に黒いマスが1つ以上あるマスの数がわかる。黒のマスが0の3x3は(h-2)*(w-2) - (1~9の合計)で出るので問題ない。
具体的な実装方法は、与えられた黒のマスが、3x3のマスで左上、上、右上、左、真ん中、右、左下、下、右下になるような場合を考えたいので、黒のマスの周りの9個の座標を3x3の中心 (cx,cy)とする場合を考える。次に、(cx,cy)を中心とした、3x3にいくつ黒いマスがあるかを調べていく。ただし、重複して同じ3x3を調べないように、setに調べた(cx,cy)を入れておく。
ミス
時間がかかってしまった。
コード
#include <iostream> #include <algorithm> #include <set> #include <cstdio> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int dy[] = {1, 1, 0, -1, -1, -1, 0, 1, 0}; int dx[] = {0, 1, 1, 1, 0, -1, -1, -1, 0}; int x[100010], y[100010]; int main(void){ int h, w, n; cin >> h >> w >> n; set<pair<int, int> > s; set<pair<int, int> > used; rep(i, n){ int a, b; cin >> a >> b; a--; b--; y[i] = a; x[i] = b; s.insert(make_pair(a, b));//y,x } ll ans[10]; rep(i, 10) ans[i] = 0; rep(i, n){ rep(j, 9){ //黒の周りから3x3の真ん中となりうるものをcy,cx int cy = y[i] + dy[j], cx = x[i] + dx[j]; if(!(0 <= cy && cy < h && 0 <= cx && cx < w)) continue; if(used.count(make_pair(cy, cx)) == 1)continue;//すでに調べた int tmp = 0; rep(k, 9){//cy,cxを中心とした3x3を調べる int ny = cy + dy[k], nx = cx + dx[k]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) break; if(s.count(make_pair(ny, nx)) == 1)tmp++; if(k == 8){ used.insert(make_pair(cy, cx)); ans[tmp]++; } } } } ll sum = 0; rep(i, 10){//1~9の合計 sum += ans[i]; } //0は全ての3x3から1~9の合計を引けばいい printf("%lld\n", ((ll)h - 2) * ((ll)w - 2) - sum); for (int i = 1; i <= 9; ++i){ printf("%lld\n", ans[i]); } return 0; }