ABC 045 D - すぬけ君の塗り絵 ( Ad hoc )

D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Beginner Contest 045 | AtCoder
考慮每個點在分別在九宮格的每個可能位置上的那九宮格數量。對於每個那樣的點那樣的位置，增加對應的塗色數計數。由於包含 x 個點的九宮格會被算 x 次，最後要做一次除法得到正確答案。

#include <bits/stdc++.h>
using namespace std;
 
typedef vector< int > vi;
typedef long long ll;
typedef vector< ll > vl;
typedef pair< int, int > pii;
 
int H, W, N;
vi A, B;
 
void init(){
    cin >> H >> W >> N;
    A = vi( N );
    B = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ] >> B[ i ],
        --A[ i ], --B[ i ];
}
 
const int dx[] = { 0, 0, 0, 1, 1, 1, 2, 2, 2 };
const int dy[] = { 0, 1, 2, 0, 1, 2, 0, 1, 2 };
 
bool in_range( int x, int y ){
    return 0 <= x and x < H and 0 <= y and y < W;
}
 
bool sqr_in_range( int x, int y ){ // left-top ( x, y ), size 3 * 3
    for( int di = 0; di < 9; ++di )
        if( not in_range( x + dx[ di ], y + dy[ di ] ) )
            return false;
    return true;
}
 
int count_black( int x, int y, const set< pii > &st ){
    if( not sqr_in_range( x, y ) )
        return 0; // !!! dump
    int cnt = 0;
    for( int di = 0; di < 9; ++di )
        cnt += st.count( pii( x + dx[ di ], y + dy[ di ] ) );
    return cnt;
}
 
void solve(){
    vl ans( 10 );
    set< pii > pnt;
    for( int i = 0; i < N; ++i )
        pnt.insert( pii( A[ i ], B[ i ] ) );
 
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < 9; ++j )
            ++ans[ count_black( A[ i ] - dx[ j ], B[ i ] - dy[ j ], pnt ) ];
 
    ll psum = 0;
    for( int i = 1; i < 10; ++i )
        ans[ i ] /= i,
        psum += ans[ i ];
 
    ll tot = 1LL * ( H - 3 + 1 ) * ( W - 3 + 1 );
    ans[ 0 ] = tot - psum;
 
    for( int i = 0; i < 10; ++i )
        cout << ans[ i ] << "\n";
}
 
signed main(){
    ios::sync_with_stdio( 0 );
    init();
    solve();
    return 0;
}