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

Re:深搜简单吧!如果改广搜,怎么改?

Posted by soga at 2008-08-16 11:53:09 on Problem 1562
In Reply To:深搜简单吧!如果改广搜,怎么改? Posted by:zhb_msqx at 2007-08-23 15:47:19
#include<stdio.h>

struct
{
   int n;
   int m;
} queue[100000];

int m, n;

void traverse(int i, int j, char **table)
{
    int front=-1, rear=0;
    int m1=i;
    int n1=j;
    table[i][j]='*';
    queue[rear].m=i;
    queue[rear].n=j;
    while (front<rear)
    {
       ++front;
       i=queue[front].m;
       j=queue[front].n;
       for (int d=0; d!=8; ++d)
       {
          switch (d)
          {
            case 0: {
                       m1 = i;
                       n1 = j-1;
                    } break;
            case 1: {
                       m1 = i-1;
                       n1 = j-1;
                    } break;
            case 2: {
                       m1 = i-1;
                       n1 = j;
                    } break;
            case 3: {
                       m1 = i-1;
                       n1 = j+1;
                    } break;
            case 4: {
                       m1 = i;
                       n1 = j+1;
                    } break;
            case 5: {
                       m1 = i+1;
                       n1 = j+1;
                    } break;
            case 6: {
                       m1 = i+1;
                       n1 = j;
                    } break;
            case 7: {
                       m1 = i+1;
                       n1 = j-1;
                    } break;
            
          }
          if (n1<0 || n1>=n || m1<0 || m1>=m)
             continue;
          if (table[m1][n1]=='@')
          {
             table[m1][n1]='*';
             ++rear;
             queue[rear].m=m1;
             queue[rear].n=n1;
          }
       }
    }
}

int main()
{
    while (scanf("%d %d",&m, &n), m!=0)
    {
       char ch;
       char **table=new char*[m];
       for (int i=0; i!=m; ++i)
          table[i]=new char[n+1];
       for (int i=0; i!=m; ++i)
          scanf("%s", table[i]);
       int max=0;
       int test=0;
       for (int i=0; i!=m; ++i)
          for (int j=0; j!=n; ++j)
          {
             if (table[i][j]=='*')
                continue;
             traverse(i, j, table);
             ++max;
          }
       printf("%d\n", max);
       delete table;
    }
    return 0;
}
耗时0ms,内存352k

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