srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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;
}