关于杭电一题搜索题目，很困扰
杭电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 prison all his life.";
}
return 0;
}
希望大家给点帮助
[解决办法]
我的，你可以参考参考
- C/C++ code
#include <stdio.h>#include <string.h>#include <queue>using namespace std;#define M 201char 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 prison all his life.\n"); else printf("%d\n",ans); } return 0;}