2 条题解

  • 0
    @ 2025-10-8 16:54:06
    #include<bits/stdc++.h>
    using namespace std;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    bool Map[110][110];
    bool bk=false;
    int n,m;
    int f[110][110][4];
    int stx,sty,edx,edy;
    void dfs(int x,int y,int t,int s)
    {
        if(s>f[x][y][t]) return;
        
        f[x][y][t]=s;
        
        if(x==edx && y==edy){bk=true;return;}
        else
        {
            for(int i=0;i<=3;i++)
            {
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(Map[xx][yy])
                {
                    Map[xx][yy]=0;
                    dfs(xx,yy,i,s+(i!=t));
                    Map[xx][yy]=1;
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        memset(Map,0,sizeof(Map));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int x;scanf("%d",&x);Map[i][j]=(x==0);
            }
        }
        scanf("%d%d",&stx,&sty);
        scanf("%d%d",&edx,&edy);
        
        memset(f,63,sizeof(f));
        Map[stx][sty]=0;
        bk=false;for(int i=0;i<=3;i++)dfs(stx,sty,i,0);
        
        if(bk==0) printf("-1\n");
        else
        {
            int ans=999999999;for(int i=0;i<=3;i++)ans=min(ans,f[edx][edy][i]);
            printf("%d\n",ans);
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:53:49
      #include<bits/stdc++.h>
      using namespace std;
      int dx[4]={-1,1,0,0};
      int dy[4]={0,0,-1,1};
      bool Map[110][110],bk=False;
      int n,m;
      int f[110][110][4];
      int stx,sty,edx,edy;
      void dfs(int x,int y,int t,int s)
      {
          if(s>f[x][y][t]) return;
          
          f[x][y][t]=s;
          
          if(x==edx && y==edy){bk=True;return;}
          else
          {
              for(int i=0;i<=3;i++)
              {
                  int xx=x+dx[i];
                  int yy=y+dy[i];
                  if(Map[xx][yy])
                  {
                      Map[xx][yy]=0;
                      dfs(xx,yy,i,s+(i!=t)) ;
                      Map[xx][yy]=1;
                  }
              }
          }
      }
      int main()
      {
          scanf("%d%d",&n,&m);
          memset(Map,0,sizeof(Map));
          for(int i=1;i<=n;i++)
          {
              for(int j=1;j<=m;j++)
              {
                  int x;scanf("%d",&x);Map[i][j]=(x==0);
              }
          }
          scanf("%d%d",&stx,&sty);
          scanf("%d%d",&edx,&edy);
          
          memset(f,63,sizeof(f));
      	Map[stx][sty]=0;
          bk=0;for(int i=0;i<=3;i++)dfs(stx,sty,i,0);
          
          if(bk==0) printf("-1\n");
          else
          {
          	int ans=999999999;for(int i=0;i<=3;i++)ans=min(ans,f[edx][edy][i]);
      		printf("%d\n",ans);
          }
          return 0;
      }
      • 1

      信息

      ID
      778
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      90
      已通过
      20
      上传者