石油采集

dfs解法：
首先我们来对题目中的这句话进行分析：“这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）”，不难理解就是只能采集“日”字型区域的石油（“日”字可以正着放也可以转90度放置），之后可以发现满足条件的油田满足一个条件，即其坐标(x,y)之和x+y满足一奇一偶，所以我们分别统计为奇数的个数ans1和偶数的个数ans1，由于奇偶要配对所以取min(ans1,ans2)。

#include <stdio.h>
#define N 1000
int n,m,book[N][N],ans1=0,ans2=0;
char f[N][N];
int next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int min(int n,int m){
    return n>m?m:n;
}
void dfs(int x,int y){
    if((x+y)%2){  
        ans1++; 
    }else{
        ans2++;
    }
    int tx,ty;
    for(int k=0;k<4;k++){
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<0||ty<0||tx>=m||ty>=m){
            continue;
        }
        if(f[tx][ty]=='#'&&book[tx][ty]==0){
            book[tx][ty]=1;
            dfs(tx,ty);
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    int cnt1=0;
    while(n--){
        int sum=0;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%s",f[i]);
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                book[i][j]=0;
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(f[i][j]=='#'&&book[i][j]==0){
                    ans1=0;ans2=0;
                    book[i][j]=1;
                    dfs(i,j);
                    sum=sum+min(ans1,ans2);
                }
            }
        }
        printf("Case %d: %d\n",++cnt1,sum);
    }    

    return 0;
}