题意：一个m*n的矩阵，k个炮台，人物要在d个单位时间内从(0,0)走到(m,n)，并给出每架炮台的发射方向、发射时间间隔、炮弹速度、坐标，求人物到达终点的最短时间；
思路：bfs,每走一步都判断一下四个方向是否有危险以确定是否能走这一步，并且不能走到炮台上！！！考虑要周全，vis用bool写，否则超内存；感觉搜索蛮锻炼代码能力的；
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; bool vis[105][105][1005];//改为int就会超内存 int dir[5][2]={{-1,0},{0,1},{1,0},{0,-1},{0,0}}; int m,n,k,d; int judge(int a,int b)//是否在地图内 { if(a<0||a>m||b<0||b>n) return 0; return 1; } struct node { int x,y,t; };//人物 struct Node { int v,t; char s; }shot[105][105];//炮台 void bfs() { int flag,dis,temp,i,j; node cur,now; memset(vis,false,sizeof(vis)); queue<node> q; node s; s.x=s.y=s.t=0; q.push(s); vis[0][0][0]=true; while(!q.empty()) { cur=q.front(); q.pop(); if(cur.t>d) break; if(cur.x==m&&cur.y==n)//到达终点，记得写在for的外面！ { printf("%d ",cur.t); return; } for(i=0;i<5;i++) { now.x=cur.x+dir[i][0]; now.y=cur.y+dir[i][1]; now.t=cur.t+1; if(!judge(now.x,now.y)||vis[now.x][now.y][now.t]||now.t>d) continue; if(shot[now.x][now.y].t) continue;//不能走到炮台上，这个判定非常重要，导致花了一个晚上找这个bug flag=1; for(j=now.x-1;j>=0;j--) { if(shot[j][now.y].t&&shot[j][now.y].s=='S')//当前位置北边是否有向南射的炮 { dis=now.x-j; if(dis%shot[j][now.y].v) break; temp=now.t-dis/shot[j][now.y].v; if(temp<0) break;//人物到达该位置是不曾有炮经过 if(temp%shot[j][now.y].t==0)//人物被击中 { flag=0;break; } } if(shot[j][now.y].t) break;//若有炮台挡住，则人物北边无危险 } if(!flag) continue;//当前位置危险，不能走 for(j=now.x+1;j<=m;j++) { if(shot[j][now.y].t&&shot[j][now.y].s=='N')//检测南边 { dis=j-now.x; if(dis%shot[j][now.y].v) break; temp=now.t-dis/shot[j][now.y].v; if(temp<0) break; if(temp%shot[j][now.y].t==0) { flag=0;break; } } if(shot[j][now.y].t) break; } if(!flag) continue; for(j=now.y-1;j>=0;j--) { if(shot[now.x][j].t&&shot[now.x][j].s=='E')//检测西边 { dis=now.y-j; if(dis%shot[now.x][j].v) break; temp=now.t-dis/shot[now.x][j].v; if(temp<0) break; if(temp%shot[now.x][j].t==0) { flag=0; break; } } if(shot[now.x][j].t) break; } if(!flag) continue; for(j=now.y+1;j<=n;j++) { if(shot[now.x][j].t&&shot[now.x][j].s=='W')//检测东边 { dis=j-now.y; if(dis%shot[now.x][j].v) break; temp=now.t-dis/shot[now.x][j].v; if(temp<0) break; if(temp%shot[now.x][j].t==0) { flag=0; break; } } if(shot[now.x][j].t) break; } if(!flag) continue; vis[now.x][now.y][now.t]=true; q.push(now); } } printf("Bad luck! "); } int main() { int i,j,v,t,x,y; char s; while(scanf("%d%d%d%d",&m,&n,&k,&d)!=EOF) { memset(shot,0,sizeof(shot)); for(i=0;i<k;i++) { scanf(" %c %d%d%d%d",&s,&t,&v,&x,&y);//所有炮台信息 shot[x][y].s=s; shot[x][y].t=t; shot[x][y].v=v; } bfs(); } return 0; }