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