1 条题解

  • 0
    @ 2025-2-14 21:09:17

    C :

    #include<stdio.h>
    #include<string.h>
    #define min(x,y) x>y?y:x
    int a,b,c,d,p;
    char map[103][103];
    void dfs(int x,int y,int s)
    {
        if(map[x][y]=='#')return ;
        if(x==c && y==d ){p=min(s,p);return ;}
        s++;
        map[x][y]='#';
        dfs(x+1,y,s);
        dfs(x,y+1,s);
        dfs(x-1,y,s);
        dfs(x,y-1,s);
        map[x][y]='-';
    }
    int main()
    {
       // freopen("sousuo.txt","w",stdout);
        int T,n,m,i,j;
        scanf("%d",&T);
        while(T--)
        {
            memset(map,'#',sizeof(map));
            scanf("%d%d",&n,&m);
            for(i=1;i<=n;++i)
            {
                getchar();
                for(j=1;j<=m;++j)
                {
                    map[i][j]=getchar();
                    if(map[i][j]=='S'){a=i;b=j;}
                    if(map[i][j]=='E'){c=i;d=j;}
                }
            }
            p=11000;
            dfs(a,b,0);
            printf("%d\n",p);
        }
        return 0;
    }
    
    

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define min(x,y) x<y?x:y;
    bool flag;
    int x1,y1,x2,y2,a,b,m;
    char map[103][103];
    void dfs(int i,int j,int cnt)
    {
    
        if(map[i][j]=='#') return ;
        if(i==x2&&j==y2)
        {
            m=min(cnt,m);
            flag= false;
            return ;
        }
        if(i>=1&&i<=a&&j>=1&&j<=b&&map[i][j]!='#')
        {
            cnt++;
            map[i][j]='#';
            dfs(i,j-1,cnt);
            dfs(i-1,j,cnt);
            dfs(i,j+1,cnt);
            dfs(i+1,j,cnt);
            map[i][j]='-';
        }
    }
    int main()
    {
        int T,i,j;
        cin>>T;
        while(T--)
        {
            m = 100000;flag = true;
            scanf("%d%d",&a,&b);
            for(i = 1 ; i <= a; i++)
            {
                for(j = 1 ; j <= b; j++)
                {
                    cin>>map[i][j];
                    if(map[i][j]=='S')
                        x1=i,y1=j;
                    if(map[i][j]=='E')
                    {
                        x2=i,y2=j;
                    }
                }
            }
            dfs(x1,y1,0);
            if(!flag)
            printf("%d\n",m);
            else
            printf("-1\n");
        }
        return 0;
    }
    
    

    Pascal :

    program maze_problem;
    const dx:array[1..4]of integer=(0,1,0,-1);
          dy:array[1..4]of integer=(1,0,-1,0);
    var dui:array[1..10000,1..3]of integer;
        gr:array[1..200,1..200]of integer;
        i,j,k,n,x,y,fx,fy,nx,ny,t,times,m:integer;
        head,tail:integer;
        s:string;
        find:boolean;
    procedure count(x,y:integer);
    var i:integer;
    begin
      dui[head,1]:=x;
      dui[head,2]:=y;
      dui[head,3]:=1;
      while head<=tail do
        begin
          for i:=1 to 4 do
            begin
              nx:=dui[head,1]+dx[i];
              ny:=dui[head,2]+dy[i];
              if (nx>0)and(nx<=n)and(ny>0)and(ny<=m) then
                begin
                  if gr[nx,ny]=0 then
                    begin
                      inc(tail);
                      gr[nx,ny]:=1;
                      dui[tail,1]:=nx;
                      dui[tail,2]:=ny;
                      dui[tail,3]:=dui[head,3]+1;
                      if (nx=fx)and(ny=fy) then
                        begin
                          find:=true;
                          times:=dui[tail,3];
                          exit;
                        end;{then-final}
                    end;{then-n}
                end;{then-nn}
            end;{for-i}
          inc(head);
        end{while}
    end;{count}
    procedure init;
    begin
      readln(t);
      for i:=1 to t do
        begin
          readln(n,m);
          fillchar(gr,sizeof(gr),0);
          for j:=1 to n do
            begin
              readln(s);
              for k:=1 to m do
                begin
                  if s[k]='-' then gr[j,k]:=0;
                  if s[k]='#' then gr[j,k]:=1;
                  if s[k]='E' then
                    begin
                      fx:=j;
                      fy:=k;
                      gr[j,k]:=0;
                    end;{then_E}
                  if s[k]='S' then
                    begin
                      x:=j;
                      y:=k;
                      gr[j,k]:=1;
                    end;{then-S}
                end;{for-k}
            end;{for-j}
          head:=1;
          tail:=1;
          find:=false;
          count(x,y);
          if find then writeln(times-1)
          else writeln('-1');
        end;{for-i}
    end;{init}
    begin{main}
      init;
    end.
    
    • 1

    信息

    ID
    650
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者