HOJ 3130 Qie-Gao -----------BFS
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.zzzyk.com
<m; 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;
}
补充：软件开发 , C++ ,
