首页 > 代码库 > 第三方
第三方
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef struct node
{
int x,y,ans,num,pre;
friend bool operator<(struct node a,struct node b)//现在还不懂啊
{
return a.ans>b.ans;
}
} st;
st qq[100001];
int n,m;
char map[101][101];
int v[101][101];
int jx[]= {1,-1,0,0};
int jy[]= {0,0,1,-1};
int judge(int x,int y)
{
if(x>=n||y>=m||x<0||y<0)
return 0;
if(map[x][y]==‘X‘)
return 0;
return 1;
}
void bfs()
{
int flag=0,tt=1;
memset(v,0,sizeof(v));
priority_queue <st> q;
st t,f;
t.x=0;
t.y=0;
t.ans=0;
t.num=1;
t.pre=-1;
q.push(t);
v[0][0]=1;
while(!q.empty())
{
t=q.top();
q.pop();
if(t.x==n-1&&t.y==m-1)
{
flag=1;
return ;
}
for(int i=0; i<4; i++)
{
f.x=t.x+jx[i];
f.y=t.y+jy[i];
if(v[f.x][f.y]==0&&judge(f.x,f.y))
{
if(map[f.x][f.y]==‘.‘)
{
f.ans=t.ans+1;
v[f.x][f.y]=1;
tt++;
f.num=tt;
f.pre=t.num;
qq[tt]=f;
q.push(f);
}
else
{
f.ans=t.ans+map[f.x][f.y]-‘0‘+1;
v[f.x][f.y]=1;
q.push(f);
tt++;
f.num=tt;
f.pre=t.num;
qq[tt]=f;
q.push(f);
}
}
}
}
if(flag==0)
printf("GAME OVER.\n");
else
{
int k=p;
}
}
void print(int x)
{
int p[100001];
int ww=1;
for(int i=x; i!=-1; i=q[i].pre)
{
kj[ww++]=i;
}
//int count=0;
for(int i=ww-2; i>=0; i--)
{
if(map[qq[p[i]].x][qq[p[i]].y]==‘.‘)
printf("%ds:(%d,%d)->(%d,%d)\n",qq[p[i]].ans,qq[p[i+1]].x,qq[p[i+1]].y,qq[p[i]].x,qq[p[i]].y);
else
{
int nn = map[qq[p[i]].x][qq[p[i]].y]-‘0‘;
printf("%ds:(%d,%d)->(%d,%d)\n",qq[p[i]].ans-nn,qq[p[i+1]].x,qq[p[i+1]].y,qq[p[i]].x,qq[p[i]].y);
for(int j = 1; j <= nn ; j++)
printf("%ds:FIGHT AT (%d,%d)\n",qq[p[i]].ans-nn+j,qq[p[i]].x,qq[p[i]].y);
}
}
}
int main()
{
int i,j;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
getchar();
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < m ; j++)
cin>>map[i][j];
bfs();
cout<<"FINISH"<<endl;
}
return 0;
}
第三方