| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
5555..........大牛来看啊.....居然超时.....#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define MAX 100
struct node{
char sign;
int x;
int y;
int flag;
bool connect;
};
int cnt=0;
int dx[]={-1,1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
int m,n;
node loc[MAX][MAX];
void search(node s)
{
for(int i=0;i<8;i++)
{
int tx,ty;
tx=s.x+dx[i];
ty=s.y+dy[i];
if (tx<1 || tx>m || ty<1 ||ty >n || loc[ty][tx].sign=='*' || loc[ty][tx].connect==1) continue;
loc[ty][tx].connect=1; //如果发现有之前未遍历到的"@"则标记它
search(loc[ty][tx]);
}
}
int main()
{
//freopen("a.txt","r",stdin);
while(1)
{
cnt=0;
int i,j;
cin>>n>>m;
if(n==0) return 0;
for( i=1;i<=n;i++)
for( j=1;j<=m;j++)
{
cin>>loc[i][j].sign;
loc[i][j].flag=0;
loc[i][j].x=j;
loc[i][j].y=i;
loc[i][j].connect=0;
} //初始化
for( i=1;i<=n;i++)
for( j=1;j<=m;j++)
{
if(loc[i][j].sign=='@' && loc[i][j].connect!=1){
cnt++;
search(loc[i][j]); //如果遍历一次,发现仍然有未标记的,说明它们不连通,计数器+1,然后继续搜索
}
}
cout<<cnt<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator