单纯bfs问题。
左上角是入口迷宫，右下角是出口，有战斗在迷宫1~9后卫，他们需要击败1~9时间。
遇到怪物就能判断是什么。步骤反向输出可。
因为需要记录的步骤，队列了。
也能够使用priority_queue 优化到 0ms，
模拟queue
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<vector>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define PI 3.141592654
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,n) for(int i= a;i< n ;i++)
#define debug puts("==fuck==")
#define acfun std::ios::sync_with_stdio(false)
#define SIZE 1000+10
using namespace std;
int xx[]={0,0,-1,1};
int yy[]={-1,1,0,0};
int n,m;
char g[101][101];
struct lx
{
int x,y,lv,path;
void init(int xx,int yy,int llv,int p)
{
x=xx,y=yy,lv=llv,path=p;
}
};
lx q[10000001];
void bfs()
{
bool vis[101][101];
CLR(vis,0);
vis[0][0]=1;
lx tmp;
tmp.init(0,0,0,-1);
int h=0,e=0;
q[h++]=tmp;
bool flag=0;
while(e<h)
{
tmp=q[e++];
lx now;
// printf("%d %d ==%d
",tmp.x,tmp.y,tmp.lv);
// system("pause");
if(tmp.x==n-1&&tmp.y==m-1&&(g[tmp.x][tmp.y]<'1'||g[tmp.x][tmp.y]>'9'))
{
flag=1;
break;
}
if(g[tmp.x][tmp.y]>='1'&&g[tmp.x][tmp.y]<='9')
{
now.init(tmp.x,tmp.y,tmp.lv+1,e-1);
g[tmp.x][tmp.y]--;
vis[tmp.x][tmp.y]=1;
q[h++]=now;
}
else
FOR(k,0,4)
{
int x=tmp.x+xx[k];
int y=tmp.y+yy[k];
if(x<0||y<0||x>=n||y>=m||vis[x][y]||g[x][y]=='X')
continue;
now.init(x,y,tmp.lv+1,e-1);
vis[x][y]=1;
q[h++]=now;
}
}
if(flag)
{
stack<lx>out;
out.push(tmp);
int path=tmp.path;
int t=tmp.lv;
while(path!=-1)
{
out.push(q[path]);
path=q[path].path;
}
printf("It takes %d seconds to reach the target position, let me show you the way.
",t);
while(!out.empty())
{
lx now=out.top();out.pop();
if(now.lv==0)
{
tmp=now;
continue;
}
if(now.x==tmp.x&&now.y==tmp.y)
printf("%ds:FIGHT AT (%d,%d)
",now.lv,now.x,now.y);
else
printf("%ds:(%d,%d)->(%d,%d)
",now.lv,tmp.x,tmp.y,now.x,now.y);
tmp=now;
}
}
else
puts("God please help our poor hero.");
puts("FINISH");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
char str[101];
FOR(i,0,n)
{
scanf("%s",str);
FOR(j,0,m)
g[i][j]=str[j];
}
bfs();
}
}
priority_queue版本号
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<vector>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define PI 3.141592654
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,n) for(int i= a;i< n ;i++)
#define debug puts("==fuck==")
#define acfun std::ios::sync_with_stdio(false)
#define SIZE 100+10
using namespace std;
int xx[]={0,0,-1,1};
int yy[]={-1,1,0,0};
int n,m;
char g[SIZE][SIZE];
struct lx
{
int x,y,lv,path,now;
void init(int xx,int yy,int llv,int p,int n)
{
x=xx,y=yy,lv=llv,path=p,now=n;
}
friend bool operator< (lx a,lx b)
{
return a.lv>b.lv;
}
}que[10100];
lx start;
void bfs()
{
priority_queue<lx>q;
start.init(0,0,0,-1,0);
bool vis[SIZE][SIZE];
CLR(vis,0);
vis[0][0]=1;
int h=0;
que[h++]=start;
q.push(start);
bool flag=0;
lx tmp;
while(!q.empty())
{
tmp=q.top();
q.pop();
// printf("%d %d==%d
",tmp.x,tmp.y,tmp.lv);
// system("pause");
if(tmp.x==n-1&&tmp.y==m-1)
{
flag=1;
break;
}
FOR(k,0,4)
{
int x=tmp.x+xx[k];
int y=tmp.y+yy[k];
if(x<0||y<0||x>=n||y>=m||g[x][y]=='X'||vis[x][y])
continue;
if(g[x][y]>='1'&&g[x][y]<='9')
que[h].init(x,y,tmp.lv+g[x][y]-'0'+1,tmp.now,h);
else
que[h].init(x,y,tmp.lv+1,tmp.now,h);
q.push(que[h++]);
vis[x][y]=1;
}
}
if(flag)
{
printf("It takes %d seconds to reach the target position, let me show you the way.
",tmp.lv);
stack<lx>out;
int path=tmp.now;
while(path!=-1)
{
out.push(tmp);
path=tmp.path;
tmp=que[path];
}
lx now;
while(!out.empty())
{
tmp=out.top();
out.pop();
if(tmp.lv==0)
{
now=tmp;
continue;
}
if(tmp.lv-now.lv==1)
printf("%ds:(%d,%d)->(%d,%d)
",tmp.lv,now.x,now.y,tmp.x,tmp.y);
else
{
printf("%ds:(%d,%d)->(%d,%d)
",++now.lv,now.x,now.y,tmp.x,tmp.y);
while(now.lv++<tmp.lv)
printf("%ds:FIGHT AT (%d,%d)
",now.lv,tmp.x,tmp.y);
}
now=tmp;
}
}
else
puts("God please help our poor hero.");
puts("FINISH");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
char str[SIZE];
FOR(i,0,n)
{
scanf("%s",str);
FOR(j,0,m)
{
g[i][j]=str[j];
}
}
bfs();
}
}
版权声明：本文博主原创文章，博客，未经同意不得转载。