Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

5555..........大牛来看啊.....居然超时.....

Posted by c4pt0r at 2007-06-14 17:17:13 on Problem 1562
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator