1 solutions

  • 0
    @ 2024-12-11 0:16:56

    C++ :

    #include<iostream>
    using namespace std;
    int n,x1,x2,y1,y2,h=0,r=1;;
    char a[1001][1001];
    int b[1000000][4],c[1001][1001]={0};
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    void bfs();
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;++i)
    	for(int j=1;j<=n;++j)
    	cin>>a[i][j];
    	cin>>x1>>y1>>x2>>y2;
    	bfs();
    	return 0;
    	
    }
    void bfs()
    {
    	int x,y;
    	b[1][1]=x1;
    	b[1][2]=y1;
    	b[1][3]=0;
    	c[x1][y1]=1;
    	while(h<r)
    	{
    		++h;
    		for(int i=0;i<4;++i)
    		{
    			x=b[h][1]+dx[i];
    			y=b[h][2]+dy[i];
    			if(x>0&&x<=n&&y>0&&y<=n&&!c[x][y]&&a[x][y]=='0')
    			{
    				c[x][y]=1;
    				++r;
    				b[r][1]=x;
    				b[r][2]=y;
    				b[r][3]=b[h][3]+1;
    			}
    			if(x==x2&&y==y2)
    			{
    				cout<<b[r][3];
    				return;
    			}
    		}
    	}
    }
    

    Pascal :

    const maxn=1000;
    dx:array[1..4] of longint=(0,1,0,-1);
    dy:array[1..4] of longint=(1,0,-1,0);
    var x1,y1,x2,y2,n,i,j,fp,rp:longint;
    ch:char;
    a:array[1..maxn,1..maxn] of record
    num,road:longint;
    end;
    q:array[1..maxn*maxn] of record
    x,y,route:longint;
    end; procedure search(i,j:integer);
    var k:longint;
    begin
    q[1].x:=x1; q[1].y:=y1; q[1].route:=0;
    fp:=1; rp:=1;
    repeat
    for k:=1 to 4 do
    if (q[fp].x+dx[k]>=1) and (q[fp].x+dx[k]<=n) and (q[fp].y+dy[k]>=1)
    and (q[fp].y+dy[k]<=n) and (a[q[fp].x+dx[k],q[fp].y+dy[k]].num=0) then
    begin
    inc(rp);
    q[rp].x:=q[fp].x+dx[k];
    q[rp].y:=q[fp].y+dy[k];
    q[rp].route:=q[fp].route+1;
    a[q[rp].x,q[rp].y].road:=q[rp].route;
    a[q[rp].x,q[rp].y].num:=1;
    end;
    inc(fp);
    until fp>rp;
    end; begin
    readln(n);
    for i:=1 to n do
    begin
    for j:=1 to n do
    begin
    read(ch);
    a[i,j].num:=ord(ch)-ord('0');
    end;
    readln;
    end;
    readln(x1,y1,x2,y2);
    search(x1,y1);
    writeln(a[x2,y2].road);
    end.
    
    • 1

    Information

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