1 条题解

  • 1
    @ 2022-09-01 20:03:43
    #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

信息

ID
1613
难度
8
分类
搜索 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者