Bài 2 : ( 6 điểm ) Lưới
Cho lưới ô vuông gồm N dòng M cột . Trong mỗi ô của lưới chỉ chứa số 0 hoặc 1 . Một ô vuông ở dòng x cột y kí hiệu là (x,y) . Từ 1 ô vuông có thể di chuyển sang 4 ô vuông chung cạnh . Một vùng là tập hợp các ô kề cạnh với nhau và có giá trị bằng nhau . Cho trước 2 ô (x1,y1) và (x2,y2) . Hãy cho biết hai ô đã cho có thuộc cùng một vùng hay không ?
Dữ liệu vào : LUOI.INP
- Dòng 1 L Ghi 2 số N , M . (1<=N , M<=100) .
- Dòng 2 : Ghi 4 số x1,y1,x2,y2 . (1<=x1,x2<=N ; 1<=y1,y2<=M)
Dữ liệu ra : LUOI.OUT
- Gồm 1 dòng : Ghi Yes nếu 2 ô (x1,y1) và (x2,y2) cùng thuộc 1 vùng .
Ghi No nếu 2 ô (x1,y1) và (x2,y2) không thuộc 1 vùng .
Vd: LUOI.INP
5 7
1 1 3 2
1 1 1 1 1 1 1
1 1 0 0 1 0 0
1 1 1 0 0 0 1
1 0 0 0 1 0 1
1 0 1 1 1 0 1
LUOI.OUT
Yes
Link tải bài giải :
[You must be registered and logged in to see this link.]__________________________________________________________________
- Code:
]Program Bai1;
Const fi = 'luoi.inp';
fo = 'luoi.out';
Vx : Array [1..4] Of Integer = (-1,1,0,0);
Vy : Array [1..4] Of Integer = (0,0,1,-1);
Var A : Array [1..100,1..100] Of Integer;
kx,ky : Array [1..100] Of Integer;
d,i,j,n,m : Integer;
c,q,w,e,r : Integer;
f,g : Text;
Procedure doctep;
Var i,j : Integer;
Begin
Assign(f,fi);
Reset(f);
Readln(f,n,m);
Readln(f,q,w,e,r);
For i:=1 to n do
Begin
For j:=1 to m do
Read(f,a[i,j]);
Readln(f);
End;
Close(f);
c:=0; d:=1;
End;
Procedure them(x,y : Integer);
Begin
inc(c);
kx[c]:=x;
ky[c]:=y;
End;
Procedure rut(Var x,y : Integer);
Begin
x:=kx[d];
y:=ky[d];
inc(d);
End;
Function ktra(x,y : Integer) : Boolean;
Begin
ktra:=false;
If ( 1<=x ) and ( x<=n ) and ( 1<=y ) and ( y<=m ) then
ktra:=true;
End;
Procedure try(x,y : Integer);
Var i,j,xo,yo : Integer;
Begin
them(x,y);
a[x,y]:=2;
While c >= d do
Begin
rut(x,y);
For i:=1 to 4 do
Begin
xo:=x+Vx[i];
yo:=y+Vy[i];
If (a[xo,yo]=1) and (ktra(xo,yo)=true) then
Begin
them(xo,yo);
A[xo,yo]:=2;
End;
End;
End;
End;
Procedure ghi;
Var i,j : Integer;
Begin
Assign(g,fo);
Rewrite(g);
If (a[q,w] <> a[e,r]) then Writeln(g,'No')
Else
Begin
try(q,w);
If a[e,r]=2 then Writeln(g,'Yes')
Else Writeln(g,'No');
End;
Close(g);
End;
Begin
doctep;
ghi;
End.