HOJ 3130 Qie-Gao -BFS

HOJ 3130 Qie-Gao -----------BFS

HOJ 3130 Qie-Gao

//题意：此处略去好多字//思路：BFS 记录搜索的起点和终点，//      然后把他们所围的矩形的大小求出，然后再与搜索的步数比较，如果相等，说明这是切糕，不等不是//hint:......//     做啦一天搜索题目，这个题最有快感啦，一次a，貌似没有什么收获，//     大一的秋季校赛题，表示也不过如此啊，为什么我当年校赛只a啦一题，擦，睡觉，哈哈#include<iostream>#include<queue>#include<cstring>#define maxlen 1010using 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;}