学步园

HOJ 3130 Qie-Gao

//题意：此处略去好多字
//思路：BFS 记录搜索的起点和终点，
//      然后把他们所围的矩形的大小求出，然后再与搜索的步数比较，如果相等，说明这是切糕，不等不是
//hint:......
//     做啦一天搜索题目，这个题最有快感啦，一次a，貌似没有什么收获，
//     大一的秋季校赛题，表示也不过如此啊，为什么我当年校赛只a啦一题，擦，睡觉，哈哈
#include<iostream>
#include<queue>
#include<cstring>
#define maxlen 1010
using namespace std;
int mat[maxlen][maxlen];
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
inline int abs(int a)
{
	return a > 0 ? a : -a;
}
struct node
{
    int x;
    int y;
};
int BFS(node s,int m,int n)
{
    node ne,ol,dr;
    int ans=0;
    queue<node> q;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    mat[s.x][s.y]=0;
    while(!q.empty())
    {
        ol=q.front();
        q.pop();
        dr.x=ol.x;
        dr.y=ol.y;
        ans++;
        for(int i=0; i<4; i++)
        {
            ne.x=ol.x+dir[i][0];
            ne.y=ol.y+dir[i][1];
            if(ne.x<0||ne.y<0||ne.x>m-1||ne.y>n-1||mat[ne.x][ne.y]==0)continue;
            else
            {
                mat[ne.x][ne.y]=0;
                q.push(ne);
            }
        }
    }
    if(ans!=(abs(s.x-dr.x)+1)*(abs(s.y-dr.y)+1)) return -1;
    else return ans;
}
int main()
{
    bool flag;
    int m,n,i,j,sum,count;
    char k;
    node s;
    while(cin >> m >> n&&m&&n)
    {
        memset(mat,0,sizeof(mat));
        flag=true,sum=0;
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
            {
                cin >> k;
                if(k=='#') mat[i][j]=1;
            }
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
                if(mat[i][j]==1)
                {
                    s.x=i;
                    s.y=j;
                    count=BFS(s,m,n);
                    if(count>0) sum++;
                    else flag=false;
                }
        if(flag)  cout << sum << endl;
        else cout <<"Oh!My God!" << endl;
    }
    return 0;
}