| ||||||||||
| 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 | |||||||||
Re:深搜简单吧!如果改广搜,怎么改?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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator