关于杭电一题搜寻题目，很困扰

关于杭电一题搜索题目，很困扰
杭电OJhttp://acm.hdu.edu.cn/showproblem.php?pid=1242我用的广度优先遍历。。这种搜索要用一个数组来标记访问过的吗，我前天刚做了题没用提交成功了，今天交了内存超了，于是我就加了标记数组，可是就错了，我做过的几题广搜的都是一加这个就错，所以我都没用标记数组，下面是我的代码我把标记数组注释了，有人指点下该怎么加吗，我错在哪里
#include<iostream>
#include<queue>
using namespace std;
struct elem
{
int x,y;
int cost;
};
char map[50][50],visit[50][50];
int n,m,dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int bound(int x,int y)
{
if(x>=1 && y>=1 &&x<=n && y<=m)
return 1;
else
return 0;
}
int bfs(int x,int y)
{
queue<elem>q; elem a,b;
while(!q.empty()) q.pop();
a.x=x;
a.y=y;
a.cost=0;
q.push(a);
//visit[x][y]=1;
while(!q.empty())
{
b=q.front();
q.pop();
for(int i=0;i<4;i++)
{
a.x=b.x+dir[i][0];
a.y=b.y+dir[i][1];
a.cost=b.cost+1;
if(bound(a.x,a.y) && map[a.x][a.y]!='#' /*&& !visit[a.x][a.y]*/)
{
//visit[a.x][a.y]=1;
if(map[a.x][a.y]=='r')
return a.cost;
else if(map[a.x][a.y]=='x')
a.cost++;
q.push(a);

}
}
}
return -1;

}
int main()
{
int x,y;
while(cin>>n>>m)
{
memset(visit,0,sizeof(visit));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{x=i;y=j;}
}
if(bfs(x,y)!=-1)
cout<<bfs(x,y)<<endl;
else
cout<<"Poor ANGEL has to stay in the * all his life.";

}
return 0;
}
希望大家给点帮助

------解决方案--------------------
我的，你可以参考参考

C/C++ code


#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define M 201

char mat[M][M];
bool mark[M][M];
int n,m;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node
{
    int x,y,d;
}s,e,next;
int check(int i,int j)
{
    if(i>=0 && i<n && j>=0 && j<m)
        return 1;
    return 0;
}

int bfs()
{
    s.d=0;
    memset(mark,false,sizeof(mark));
    queue<node>Q;
    Q.push(s);
    mark[s.x][s.y]=true;
    while(!Q.empty())
    {
        s=Q.front();Q.pop();
        if(s.x==e.x && s.y==e.y)return s.d;
        for(int i=0;i<4;++i)
        {
            next.x=s.x+dir[i][0];
            next.y=s.y+dir[i][1];
            next.d=s.d+1;

            if(check(next.x,next.y) && !mark[next.x][next.y] && mat[next.x][next.y]!='#')
            {
                if(mat[next.x][next.y]=='x')
                {
                    next.d+=1;
                }
                //printf("-->%d %d\n",next.x,next.y);
                Q.push(next);
                mark[next.x][next.y]=true;
            }
        }
    }
    return -1;
}
void dbg()
{
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            printf("%c",mat[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int i,j;
    while(scanf("%d%d\n",&n,&m)!=EOF)
    {
        for(i=0;i<n;++i)
        {
            for(j=0;j<m;++j)
            {
                scanf("%c",&mat[i][j]);
                if(mat[i][j]=='a'){s.x=i;s.y=j;}
                if(mat[i][j]=='r'){e.x=i;e.y=j;}
            }
            getchar();
        }
        //dbg();
        int ans=bfs();
        if(ans==-1)printf("Poor ANGEL has to stay in the * all his life.\n");
        else printf("%d\n",ans);
    }
    return 0;
}

关于杭电一题搜寻题目，很困扰

相关推荐