北大acm里的题，提交时为什么提示Time Limit Exceeded,该如何改(不改变数据存储结构）才能减少运行时间？

Question

题目网址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1979
我的程序：
#include<string.h>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 400
typedef int VertexType;
typedef char InfoType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
InfoType info;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}Vnode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum;
}ALGraph;

typedef struct
{
int *elem;
int length;
}SqList;

int visited[MAX_VERTEX_NUM];
int ad = 0;

int NextAdjVex(ALGraph *G,VertexType v,VertexType w)
{
ArcNode *p;
p = G->vertices[v].firstarc;
while(p && p->adjvex != w)
p = p->nextarc;
if(!p || !p->nextarc)
return -1;
else
return p->nextarc->adjvex;
}

void DFS(ALGraph *G,int v)
{
int w;
visited[v] = 1;
ad++;
for(w = G->vertices[v].firstarc->adjvex; w >= 0;w = NextAdjVex(G,v,w = w))
if(!visited[w])
DFS(G,w);
}

int Contact(ALGraph *G,int v,int v0)
{
ArcNode *p0 = G->vertices[v0].firstarc;
if(v == v0)
return 1;
while(p0 && p0->adjvex != v)
p0 = p0->nextarc;
if(p0)
return 1;
else
return 0;
}

void Insert(ALGraph *G,int i,ArcNode node)
{
ArcNode *p;
ArcNode *q;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = node.adjvex;
p->info = node.info;
p->nextarc = NULL;
if(!G->vertices[i].firstarc)
G->vertices[i].firstarc = p;
else
{
q = G->vertices[i].firstarc;
while(q->nextarc)
q = q->nextarc;
q->nextarc = p;
}
}

void main()
{
int v = 0;
ALGraph *G;
SqList *L;
ArcNode p1[MAX_VERTEX_NUM];
int row1,row2;
int i,j;
L = (SqList*)malloc(sizeof(SqList));
G = (ALGraph*)malloc(sizeof(ALGraph));
L->elem = (int *)malloc(sizeof(int));
L->length = 1;
scanf("%d %d",&row1,&row2);
while(row1 != 0 && row2 != 0)
{
fflush(stdin);
G->vexnum = row1*row2;
for(i = 0; i < row2; i++)
{
for(j = 0; j < row1; j++)
{
scanf("%c",&p1[i*row1+j].info);
p1[i*row1+j].adjvex = i*row1+j;
p1[i*row1+j].nextarc = NULL;
if(p1[i*row1+j].info == '@')
v = i*row1+j;
if(p1[i*row1+j].info == '#')
visited[i*row1+j] = 1;
else
visited[i*row1+j] =0;
}
fflush(stdin);
}
for(i = 0; i < G->vexnum; i++)
{
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
if(i%row1 != 0)
Insert(G,i,p1[i-1]);
if((i+1)%row1 != 0)
Insert(G,i,p1[i+1]);
if(i >=row1 )
Insert(G,i,p1[i-row1]);
if(i < G->vexnum-row1)
Insert(G,i,p1[i+row1]);
}
for(i = v; i < G->vexnum; i++)
if(!visited[i] && Contact(G,i,v))
DFS(G,i);
for(i = v-1; i >= 0; i--)
if(!visited[i] && Contact(G,i,v))
DFS(G,i);
L->elem[L->length-1] = ad;
L->elem = (int *)realloc(L->elem,(L->length+1)*sizeof(int));
L->length++;
ad = 0;
scanf("%d %d",&row1,&row2);
}
for(i = 0; i < L->length-1; i++)
printf("%d\n",L->elem[i]);
}

Answer 1

#include <iostream>
using namespace std;

const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
char a[50][50];
bool b[50][50];
int n , m;

int DFS(int,int);

int main()
{
while (scanf("%d%d",&n,&m)&&n&&m)
{
int ans(0);
memset(b,0,sizeof(b));
gets(a[0]);
for (int i=0;i<m;i++)
gets(a[i]);
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
if (a[i][j] == '@')
ans += DFS(i,j);
printf("%d\n",ans);
}
return 0;
}

int DFS(int x,int y)
{
int ret(0);
if (!b[x][y]&&a[x][y]!='#')
{
ret++;
b[x][y] = 1;
for (int i=0;i<4;i++)
if (0<=x+dx[i]&&x+dx[i]<m&&0<=y+dy[i]&&y+dy[i]<n)
ret += DFS(x+dx[i],y+dy[i]);
}
return ret;
}

这个是我的代码
可以AC
在递归向下的时候需要一个新的数组记录那些点访问过
其实在同一个连通块中
用任意一个点做起点都是一样的
所以要除去重复操作
即加上一个b数组
如果某一个点被访问过
则将此点标记为已读
下次再递归到这个点的时候直接退出