传送门:【FZU】1686 神龙的难题
题目分析:又是一道水题。。。注意到他说的最多攻击的行列其实是指一个小矩形的范围。。。然后列是怪物,行是攻击,重复覆盖求最小值就行了。。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define REC( i , A , o ) for ( int i = A[o] ; i != o ; i = A[i] ) #define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXR = 230 ; const int MAXC = 230 ; const int MAXNODE = 60000 ; struct DLX { int L[MAXNODE] , R[MAXNODE] , U[MAXNODE] , D[MAXNODE] ; int row[MAXNODE] , col[MAXNODE] ; int S[MAXC] , H[MAXR] ; bool vis[MAXC] ; int deep ; int size ; int nv ; int n , m ; int maxr , maxc ; int G[16][16] ; void init () { CLR ( H , -1 ) ; FOR ( i , 0 , nv ) { S[i] = 0 ; U[i] = i ; D[i] = i ; L[i] = i - 1 ; R[i] = i + 1 ; } L[0] = nv ; R[nv] = 0 ; size = nv ; deep = MAXR ; } void link ( int r , int c ) { ++ size ; ++ S[c] ; row[size] = r ; col[size] = c ; U[size] = U[c] ; D[size] = c ; D[U[c]] = size ; U[c] = size ; if ( ~H[r] ) { L[size] = L[H[r]] ; R[size] = H[r] ; L[R[size]] = size ; R[L[size]] = size ; } else H[r] = L[size] = R[size] = size ; } void remove ( int c ) { REC ( i , D , c ) { L[R[i]] = L[i] ; R[L[i]] = R[i] ; } } void resume ( int c ) { REC ( i , U , c ) { L[R[i]] = i ; R[L[i]] = i ; } } int h () { int cnt = 0 ; CLR ( vis , 0 ) ; REC ( i , R , 0 ) if ( !vis[i] ) { ++ cnt ; vis[i] = 1 ; REC ( j , D , i ) REC ( k , R , j ) vis[col[k]] = 1 ; } return cnt ; } void dance ( int d ) { if ( d + h () >= deep ) return ; if ( R[0] == 0 ) { deep = min ( deep , d ) ; return ; } int c = R[0] ; REC ( i , R , 0 ) if ( S[c] > S[i] ) c = i ; REC ( i , D , c ) { remove ( i ) ; REC ( j , R , i ) remove ( j ) ; dance ( d + 1 ) ; REC ( j , L , i ) resume ( j ) ; resume ( i ) ; } } void solve () { nv = 0 ; REP ( i , 0 , n ) REP ( j , 0 , m ) { scanf ( "%d" , &G[i][j] ) ; if ( G[i][j] ) G[i][j] = ++ nv ; } scanf ( "%d%d" , &maxr , &maxc ) ; init () ; int r = 0 ; FOR ( i , 0 , n - maxr ) FOR ( j , 0 , m - maxc ) { ++ r ; REP ( x , i , i + maxr ) REP ( y , j , j + maxc ) if ( G[x][y] ) link ( r , G[x][y] ) ; } dance ( 0 ) ; printf ( "%d\n" , deep ) ; } } x ; int main () { while ( ~scanf ( "%d%d" , &x.n , &x.m ) ) x.solve () ; return 0 ; }