1 solutions

  • 0
    @ 2025-11-5 15:25:27

    C :

    #include<stdio.h>
    #include<string.h>
    
    struct point{
        int x,y;
        int step;
    };
    int num_x[4]={0,-1,0,1};
    int num_y[4]={-1,0,1,0};
    char a[1005][1005];
    struct point maps[1005*1005];
    int main()
    {
        int n,i,j;
        int x1,y1,x2,y2;
        while(scanf("%d",&n)!=EOF){
            memset(a,0,sizeof(a));
            for(i=0;i<n;i++)
                scanf("%s",a[i]);
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int head=1,rear=1;
            struct point st;
            st.x=x1;st.y=y1;
            st.step=0;
            a[x1-1][y1-1]='1';
            maps[rear]=st;
            rear++;
            while(head!=rear){
                struct point k=maps[head];
                ++head;
                if(k.x==x2&&k.y==y2){
                    printf("%d\n",k.step);
                    break;
                }
                for(i=0;i<4;++i){
                    struct point ss=k;
                    ss.x=k.x+num_x[i];
                    ss.y=k.y+num_y[i];
                    if(a[ss.x-1][ss.y-1]=='0'&&ss.x<=n&&ss.x>0&&ss.y<=n&&ss.y>0){
                        ss.step=k.step+1;
                        maps[rear]=ss;
                        rear++;
                        a[ss.x-1][ss.y-1]='1';
                    }
                }
            }
        }
        return 0;
    }
    

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define end END
    using namespace std;
    struct Node
    {
    	int x,y;
    	int s;
    }str,end;
    int n;
    
    int a[1201][1201],f[1201][1201];
    const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
    Node que[1201*1201];
    void bfs();
    void add(int x,int y,int s);
    int head=0,tail=1;
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	  for(int j=1;j<=n;j++)scanf("%1d",&a[i][j]);
    	cin>>str.x>>str.y>>end.x>>end.y;
    	str.s=0;
    	f[str.x][str.y]=1;
    	add(str.x,str.y,0);
    	bfs();
    	//while(1);
    	return 0;
    }
    void bfs()
    {
    	
    	while(head!=tail)
    	{
    		Node t=que[head];
    		for(int i=0;i<=3;i++)
    		{
    			int nx=t.x+dx[i];
    			int ny=t.y+dy[i];
    			if(nx>0&&ny<=n&&ny>0&&nx<=n&&a[nx][ny]==0)
    			{
    				Node k;
    				if(f[nx][ny]==0)
    				{
    					if(nx==end.x&&ny==end.y)
    					{
    						printf("%d",t.s+1);
    						return;
    					}
    					add(nx,ny,t.s+1);
    				}
    				
    			}
    		}
    		head++;
    	}
    }
    
    void add(int x,int y,int s)
    {
    	Node k;
    	k.x=x;k.y=y;k.s=s;
    	que[tail++]=k;
    	f[x][y]=1;
    }
    

    Pascal :

    const
        dx:array[1..4]of shortint=(1,-1,0,0);
        dy:array[1..4]of shortint=(0,0,-1,1);
    var n,x1,y1,x2,y2:word;
        map:array[0..1001,0..1001]of char;
        que:array[1..1000000]of record x,y,dep:word; end;
    procedure init;
    var i,j:word;
    begin
        {assign(input,'save.in');reset(input);
        assign(output,'save.out');rewrite(output);}
        fillchar(map,sizeof(map),'1');
        readln(n);
        for i:=1 to n do
            begin
                for j:=1 to n do
                    read(map[i,j]);
                readln;
            end;
        readln(x1,y1,x2,y2);
        {close(input);}
    end;{init}
    procedure work;
    var head,tail:longword;
        i:byte;
    begin
        with que[1] do begin x:=x1; y:=y1; dep:=0; end;
        head:=0;tail:=1;
        repeat
            inc(head);
            for i:=1 to 4 do
                if(que[head].x+dx[i]>0)and(que[head].x+dx[i]<=n)
                and(que[head].y+dy[i]>0)and(que[head].y+dy[i]<=n)
                and(map[que[head].x+dx[i],que[head].y+dy[i]]='0')then
                    begin
                        inc(tail);
                        with que[tail] do begin x:=que[head].x+dx[i]; y:=que[head].y+dy[i]; dep:=que[head].dep+1 end;
                        map[que[tail].x,que[tail].y]:='1';
                        if(que[tail].x=x2)and(que[tail].y=y2)then begin writeln(que[tail].dep); close(output); halt; end;
                    end;
        until head=tail;
    end;{work}
    begin{main}
        init;
        work;
    end.
    
    

    Java :

    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
        int n;
        char[][] map;
        int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
        boolean[][] mark;
    
        public static void main(String[] args) {
            Main p = new Main();
        }
    
        public Main() {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();sc.nextLine();
            map = new char[n][n];
            mark = new boolean[n][n];
            for (int i = 0; i < n ; i++) {
                String line = sc.nextLine();
                map[i] = line.toCharArray();
            }
            int start_x = sc.nextInt() - 1, start_y = sc.nextInt() - 1, end_x = sc.nextInt() - 1, end_y = sc.nextInt() - 1;
            bfs(start_x,start_y,end_x,end_y);
        }
    
        void bfs(int sx, int sy, int ex, int ey){
            ArrayList<Node> queue = new ArrayList<>();
            queue.add(new Node(sx,sy));
            while (!queue.isEmpty()){
                Node now = queue.remove(0);
                if(now.x == ex && now.y == ey) {
                    System.out.println(now.step);return;
                }
                for (int i = 0; i < 4 ; i++) {
                    int newx = now.x + dx[i], newy = now.y + dy[i];
                    if(newx>=0 && newx < n && newy >= 0 && newy < n && map[newx][newy] == '0' && !mark[newx][newy]) {
                        queue.add(new Node(newx,newy,now.step+1));
                        mark[newx][newy] = true;
                    }
                }
            }
            System.out.println("IMPOSSIBLE");
        }
    
        class Node{
            int x, y,step;
    
            public Node(int x, int y, int step) {
                this.x = x;
                this.y = y;
                this.step = step;
            }
    
            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
    
        }
    }
    
    
    • 1

    Information

    ID
    16771
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By