1 条题解
-
0Guest LV 0 MOD
-
1
#include <bits/stdc++.h> #define LL long long using namespace std; int dx[9]={0,1,1,1,0,-1,-1,-1}; int dy[9]={-1,-1,0,1,1,1,0,-1}; int dx2[5]={0,1,0,-1}; int dy2[5]={1,0,-1,0}; int m,n,e_map[50000]; char s[50000]; int st_x,st_y,ed_x,ed_y; int vis2[50000],d[50000],vis[50000]; queue<int>q; bool pd(int x,int y) { if(x<1||x>n||y<1||y>m) return 0;//return(x>0)&&(x<=n)&&(y>0)&&y<=m; return 1; } int main() { scanf("%d%d",&n,&m); //注意数组下标从0开始 数据压缩 for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=1;j<=m;j++) { if(s[j-1]=='X') e_map[(i-1)*m+j]=1; else e_map[(i-1)*m+j]=0; } } while(1) { memset(vis2,0,sizeof(vis2)); memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); int pd2=0; scanf("%d%d%d%d",&ed_x,&ed_y,&st_x,&st_y); if(ed_x==0&&ed_y==0&&st_x==0&&st_y==0) break; for(int i=0;i<8;i++) //for(int i;i=8;i++) 处理所有可能射杀敌人的所有位置 { int x=ed_x+dx[i],y=ed_y+dy[i]; while(pd(x,y)&&e_map[(x-1)*m+y]==0) { vis[(x-1)*m+y]=1; x+=dx[i],y+=dy[i]; } } q.push((st_x-1)*m+st_y); vis2[(st_x-1)*m+st_y]=1; d[(st_x-1)*m+st_y]=0; while (!q.empty()) { int k=q.front(); q.pop(); int x=k/m+1,y=k%m;////取出坐标位置 if(y==0) /// { y=m;x--; } if(vis[k]==1)/// { printf("%d\n",d[k]); pd2=1;break; } else { for(int i=0;i<4;i++) //// { int x1=x+dx2[i],y1=y+dy2[i]; if(e_map[(x1-1)*m+y1]==1||pd(x1,y1)==0) continue; if(!vis2[(x1-1)*m+y1]) { d[(x1-1)*m+y1]=d[k]+1; vis2[(x1-1)*m+y1]=1; q.push((x1-1)*m+y1); } } } } if(pd2==0) { printf("Impossible!\n"); } while(q.size()) q.pop(); } return 0; }
- 1