1 条题解

  • 0
    @ 2025-4-12 21:45:14

    C :

    #include<stdio.h>
    int main(void)
    {
        int k,x;
        scanf("%d",&x);
        for(k=1;k<=x;k++)
        {int i,j,m,n,w,i1,i2,i3,j1,j2,j3,f=0,r=1;
        char mg[105][105];
    int zg[105][105],ins[105][105],tx[4]={0,1,0,-1},ty[4]={1,0,-1,0},q[10005];
            scanf("%d%d",&n,&m);
    
        getchar();
        for(i=0;i<n;i++)
           {
            for(j=0;j<m;j++)
        scanf("%c",&mg[i][j]);
        getchar();}
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                zg[i][j]=0;
    ins[i][j]=0;
        if(mg[i][j]=='S') {i1=i;j1=j;}
            }
    q[f]=i1*m+j1;
        zg[i1][j1]=1;
    
        while(f<r)
        {w=q[f];
    
        i2=w/m;j2=w%m;
        f++;
        for(i=0;i<4;i++)
        {
    
    
            i3=i2+tx[i];j3=j2+ty[i];
            if(i3>=0&&i3<n&&j3>=0&&j3<m&&(mg[i3][j3]!='#')&&(!zg[i3][j3]))
            {zg[i3][j3]=1;
                ins[i3][j3]=ins[i2][j2]+1;
                q[r]=i3*m+j3;
                r++;
    
    }
    
        }
    }
    
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            if(mg[i][j]=='E')  if(ins[i][j]!=0) printf("%d\n",ins[i][j]);
                else printf("-1\n");
        }
    return 0;
    }
    
    
    

    C++ :

    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    
    struct MAP
    {
        int x,y,step;
    }s,e,head,tail;
    
    char g[100][100];
    int v[100][100],f[][2]={{-1,0},{0,1},{1,0},{0,-1}},n,m;
    
    int bfs()
    {
    	memset(v,0,sizeof(v));
    	queue<struct MAP> q;
    	q.push(s);
    	s.step=0;
    	v[s.x][s.y]=1;
    	while(!q.empty())
    	{
    		head=q.front();
    		q.pop();
    		for(int i=0;i<4;i++)
    		{
    			tail.x=head.x+f[i][0];
    			tail.y=head.y+f[i][1];
    			tail.step=head.step+1;
    			if(!v[tail.x][tail.y]&&g[tail.x][tail.y]!='#'&&tail.x>=0&&tail.x<n&&tail.y>=0&&tail.y<m)
    			{
    				if(tail.x==e.x&&tail.y==e.y)
    					return tail.step;
    				v[tail.x][tail.y]=1;
    				q.push(tail);
    			}
    		}
    	}
    	return -1;
    }
    
    int main()
    {
    	int t,i,j;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n>>m;
    		for(i=0;i<n;i++)
    			for(j=0;j<m;j++)
    			{
    				cin>>g[i][j];
    				if(g[i][j]=='S')
    				{
    					s.x=i;
    					s.y=j;
    				}
    				else if(g[i][j]=='E')
    				{
    					e.x=i;
    					e.y=j;
    				}
    			}
    		cout<<bfs()<<endl;
    	}
    	return 0;
    }
    

    Pascal :

    var n,m,i,j,k,p,q,ii,nn:longint;x:string;
        f:array[0..101,0..101] of longint;
        ch:array[0..101,0..101] of char;
    procedure s(x:longint);
    var i,j:longint;
     begin
      if x>n*m then begin writeln('-1');exit;end;
      for i:=1 to n do
       for j:=1 to m do
        begin
         if f[i,j]=x then
          begin
           if ch[i-1,j]='-' then f[i-1,j]:=f[i,j]+1;
           if ch[i+1,j]='-' then f[i+1,j]:=f[i,j]+1;
           if ch[i,j-1]='-' then f[i,j-1]:=f[i,j]+1;
           if ch[i,j+1]='-' then f[i,j+1]:=f[i,j]+1;
          end;
        end;
      if f[p,q]<>0 then writeln(f[p,q]-1) else s(x+1);
     end;
    begin
     readln(nn);
     for ii:=1 to nn do
     begin
     readln(n,m);
     fillchar(f,sizeof(f),0);
     for i:=1 to n do
      begin
       readln(x);
       for j:=1 to m do
        begin
         ch[i,j]:=x[j];
         if ch[i,j]='E' then begin ch[i,j]:='-'; p:=i; q:=j; end;
         if ch[i,j]='S' then f[i,j]:=1;
        end;
      end;s(1);
     end;
    end.
    

    Java :

    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    
    public class Main {
    	static int m,n;
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		int x = in.nextInt();
    		for(int ii=0;ii<x;ii++){
    			 m = in.nextInt();
    			 n = in.nextInt();
    			Node3 s = new Node3();
    			Node3 e = new Node3();
    			char[][] maze = new char[m][n];
    			for(int i=0;i<m;i++){
    				String str = in.next();
    				for(int j=0;j<n;j++){
    					maze[i][j] = str.charAt(j);
    					if(maze[i][j]=='S'){
    						s.x=i;
    						s.y=j;
    					}
    					else if(maze[i][j]=='E'){
    						e.x=i;
    						e.y=j;
    					}
    				}
    			}
    			System.out.println(bfs(maze,s,e));
    		}
    	}
    
    	public static int bfs(char[][] maze, Node3 s, Node3 e) {
    		int[][] d = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    		Queue<Node3> q = new LinkedList<Node3>();
    		q.add(s);
    		maze[s.x][s.y] = '@';
    		while (!q.isEmpty()) {
    			Node3 t = q.poll();
    			for (int i = 0; i < 4; i++) {
    				int xx = t.x + d[i][0];
    				int yy = t.y + d[i][1];
    				if (xx == e.x && yy == e.y){
    					return t.d+1;
    				}
    			}
    			for (int i = 0; i < 4; i++) {
    				int xx = t.x + d[i][0];
    				int yy = t.y + d[i][1];
    				if (xx >= 0 && xx < m && yy >= 0 && yy < n
    						&& maze[xx][yy] == '-') {
    					maze[xx][yy] = '@';
    					q.add(new Node3(xx, yy, t.d + 1));
    				}
    			}
    		}
    		return -1;
    	}
    	
    }
    class Node3{
    	int x,y,d;
    	public Node3(){
    		d = 0;
    	}
    	public Node3(int a,int b,int c){
    		x = a;
    		y = b;
    		d = c;
    	}
    }
    
    

    Python :

    # coding=utf-8
    t=int(input())
    for i in range(t):
        n,m=map(int,input().split())
        mg=[]
        for i in range(n):
            h=[]
            hstr=input()
            for j in range(m):
               h.append(hstr[j]) 
            mg.append(h)
        for i in range(n):
            for j in range(m):
                if mg[i][j]=="S":
                    x_start,y_start=i,j
        dengdai=[[x_start,y_start,0]]
        fx=[[0,-1],[0,1],[-1,0],[1,0]]
        while dengdai:
            x,y,step=dengdai.pop(0)
            for x_y in fx:
                nx,ny=x+x_y[0],y+x_y[1]
                if 0<=nx<n and 0<=ny<m and mg[nx][ny]=="E":
                    x,y,step=nx,ny,step+1
                    break
                elif 0<=nx<n and 0<=ny<m and mg[nx][ny]=="-":
                    mg[nx][ny]=step+1
                    dengdai.append([nx,ny,step+1])
            if mg[x][y]=="E":
                break
        if mg[x][y]=="E":
            print(step)
        else:
            print(-1)
    
    • 1

    信息

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