1 solutions
-
0
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