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