HOJ 3130 Qie-Gao
[cpp]
//題意：此處略去好多字
//思路：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;
} www.2cto.com
<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;
}
