題意是給你一個地圖，地圖裡有的點是炮台 炮台每隔一段時間回想固定的方向發射一定速度的炮彈，炮彈不能穿過炮台，炮彈只有只有在整點才能打中人，開始你在（0,0）的位置 問你能不能再規定的時間內走到終點；
最對100個炮台，最多走1000步 很明顯 把地圖預先處理下 及每個點在某一時間有炮彈 那麼人就不能走， 開個3維 來標記，還有 數組必須用bool型的要不然要超類存，
#include#include #include #include using namespace std; int n,m,k,d; bool map[101][101][1001]; bool mark[101][101][1001]; struct node { int x,y; int tt; }a,b; struct Node { int dir; int x,y; int t,v; }bull[110]; int dir1[4][2]={-1,0,0,1,1,0,0,-1}; int dir[5][2]={0,0,0,1,0,-1,1,0,-1,0}; int deal(int x) { int i,j; int di=bull[x].dir; int xx,yy; for(i=1;;i++) { xx=bull[x].x+i*dir1[di][0]*bull[x].v; yy=bull[x].y+i*dir1[di][1]*bull[x].v; if(xx<0||xx>n||yy<0||yy>m) break; if(map[xx][yy][0]) break; int flag=0; if(di==0) { for(j=xx;j<bull[x].x;j++) if(map[j][bull[x].y][0]) {flag=1;break;} } else if(di==1) { for(j=bull[x].y+1;j<=yy;j++) if(map[bull[x].x][j][0]) {flag=1;break;} } else if(di==2) { for(j=bull[x].x+1;j<=xx;j++) if(map[j][bull[x].y][0]){flag=1;break;} } else if(di==3) { for(j=yy;j<bull[x].y;j++) if(map[bull[x].x][j][0]) {flag=1;break;} } if(flag) break; j=0; int t=i; while(t<=d) { map[xx][yy][t]=1; j++; t=i+j*bull[x].t; } } return 0; } int bfs() { a.x=0; a.y=0; a.tt=0; memset(mark,0,sizeof(mark)); queue<node>q; mark[a.x][a.y][a.tt]=1; q.push(a); int i,j; int flash=0; while(!q.empty()) { b=q.front(); q.pop(); //printf("%d %d\n",b.x,b.y); if(b.x==n&&b.y==m) { printf("%d\n",b.tt); flash=1; break; } for(i=0;i<5;i++) { a.x=b.x+dir[i][0]; a.y=b.y+dir[i][1]; a.tt=b.tt+1; if(n-a.x+m-a.y>d-a.tt) continue; if(a.x<0||a.x>n||a.y<0||a.y>m) continue; if(map[a.x][a.y][0]) continue; if(map[a.x][a.y][a.tt]==0&&mark[a.x][a.y][a.tt]==0) { mark[a.x][a.y][a.tt]=1; q.push(a); } } } if(!flash) printf("Bad luck!\n"); return 0; } int main() { int i,j; while(~scanf("%d%d%d%d",&n,&m,&k,&d)) { char str[2]; memset(map,0,sizeof(map)); for(i=1;i<=k;i++) { scanf("%s",str); if(str[0]=='N') bull[i].dir=0; else if(str[0]=='E') bull[i].dir=1; else if(str[0]=='S') bull[i].dir=2; else if(str[0]=='W')bull[i].dir=3; scanf("%d%d",&bull[i].t,&bull[i].v); scanf("%d%d",&bull[i].x,&bull[i].y); map[bull[i].x][bull[i].y][0]=1; } for(i=1;i<=k;i++) { deal(i); } bfs(); } return 0; }
