//给一个n*m的棋盘,
//如果是
//01
//10
//的情况，可以将这两个0变成1
//给出棋盘中哪些位置是1，
//问这棋盘最后有多少1
//bfs找每一个1的斜对角是否为1
//如果找到一对斜对角为1的数
//斜对角对应的旁边的0变为1
//对于每一个新生的1其旁边的4个点的标记数组改为0
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std ;
const int maxn = 510 ;
int map[maxn][maxn] ;
int vis[maxn][maxn] ;
int X[maxn*2] , Y[maxn*2] ;
int g ;
int dx[4] = {1,1,-1,-1} ;
int dy[4] = {1,-1,-1,1};
int d_x[4] = {1,0,-1,0} ;
int d_y[4] = {0,1,0,-1} ;
int n , m;
void bfs()
{
queue<int>que ;
memset(vis , 0 , sizeof(vis));
for(int i = 1;i <= g;i++)
{
que.push(X[i]) ;
que.push(Y[i]) ;
vis[X[i]][Y[i]] = 1;
}
while(que.size())
{
int nx = que.front();que.pop() ;
int ny = que.front();que.pop() ;
for(int i = 0;i < 4;i++)
{
int px = nx + dx[i] ;
int py = ny + dy[i] ;
if(px<0||px>n||py<0||py>m)
continue ;
if(map[px][py])
{
if(!map[nx][py])
{
for(int i = 0;i < 4;i++)
vis[nx+d_x[i]][py+d_y[i]] = 0;
map[nx][py] = 1;
}
if(!map[px][ny])
{
for(int i = 0;i < 4;i++)
vis[px+d_x[i]][ny+d_y[i]] = 0;
map[px][ny] = 1 ;
}
if(!vis[nx][py])
{
que.push(nx);
que.push(py) ;
vis[nx][py] = 1;
}
if(!vis[px][ny])
{
que.push(px) ;
que.push(ny) ;
vis[px][ny] = 1;
}
}
}
}
}
int main()
{
//freopen("in.txt" , "r" , stdin) ;
int T ;
scanf("%d" , &T) ;
int cas = 0 ;
while(T--)
{
scanf("%d%d" , &n , &m) ;
memset(map , 0 , sizeof(map)) ;
int x , y ;
scanf("%d" , &g) ;
for(int i = 1;i <= g;i++)
{
scanf("%d%d" , &x, &y) ;
X[i] = x;Y[i] = y ;
map[x][y] = 1;
}
bfs() ;
int ans = 0 ;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(map[i][j]) ans++;
printf("Case #%d:\n" , ++cas) ;
printf("%d\n" , ans) ;
}
return 0;
}
hdu5254
原文：http://blog.csdn.net/cq_pf/article/details/46292469
