bài toán dò mìn
MINE.INP
MINE.OUT
3 3
1 4 2
4 5 3
2 3 3
YES
1 0 1
0 1 1
1 1 0
{**************************************************************************
* Ten FILE de bai: MINE.RTF *
* Ngay viet : 07/09/2003 *
* Nguoi viet : LE THANH BINH *
* Thuat toan : DUYET QUAY LUI *
**************************************************************************}
{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 65000,0,655360}
USES crt;
CONST
tfi = 'MINE.INP';
tfo = 'MINE.OUT';
maxMN = 100;
VAR
fi,fo : TEXT;
M,N : INTEGER;
a : ARRAY[1..maxMN,1..maxMN] OF INTEGER;
Good : BOOLEAN;
x : ARRAY[0..maxMN+1,0..maxMN+1] OF INTEGER;
PROCEDURE DOcdl;
VAR i,j: INTEGER;
BEGIN
readln(fi,M,N);
FOR i:=1 TO M DO
BEGIN
FOR j:=1 TO N DO read(fi,a[i,j]);
readln(fi);
END;
END;
PROCEDURE Duyet1;
VAR CN: BOOLEAN;
j: INTEGER;
BEGIN
good:=TRUE;
x[1,0]:=0;
FOR x[1,1]:=0 TO 1 DO
BEGIN
CN:=TRUE;
FOR j:=2 TO N DO
BEGIN
x[1,j]:=a[1,j-1]-x[1,j-2];
IF (x[1,j]<0) OR (x[1,j]>1) THEN
BEGIN
CN:=FALSE;
break;
END;
END;
CN:=CN AND (x[1,N-1]=a[1,N]);
IF CN THEN exit;
END;
Good:=FALSE;
END;
PROCEDURE Thu2(k: INTEGER);
VAR t,t1: INTEGER;
BEGIN
IF k>N THEN
BEGIN
Good:=(a[1,N]=x[1,N-1]+x[2,N-1]+x[2,N]) AND
(a[2,N]=x[2,N-1]+x[1,N-1]+x[1,N]);
exit;
END;
t:=a[1,k-1]-(x[1,k-2]+x[2,k-2]+x[2,k-1]);
t1:=a[2,k-1]-(x[2,k-2]+x[1,k-2]+x[1,k-1]);
IF t1<>t THEN exit;
CASE t OF
0: BEGIN
x[1,k]:=0; x[2,k]:=0;
Thu2(k+1);
IF Good THEN exit;
END;
1: BEGIN
x[1,k]:=0; x[2,k]:=1;
Thu2(k+1);
IF Good THEN exit;
x[1,k]:=1; x[2,k]:=0;
Thu2(k+1);
IF Good THEN exit;
END;
2: BEGIN
x[1,k]:=1; x[2,k]:=1;
Thu2(k+1);
IF Good THEN exit;
END;
END;
END;
PROCEDURE Duyet2;
BEGIN
Good:=FALSE;
fillchar(x,sizeof(x),0);
FOR x[1,1]:=0 TO 1 DO
FOR x[2,1]:=0 TO 1 DO
BEGIN
Thu2(2);
IF Good THEN exit;
END;
END;
FUNCTION CNDong(u: INTEGER): BOOLEAN;
VAR v: INTEGER;
BEGIN
CNDong:=FALSE;
FOR v:=2 TO N DO
BEGIN
x[u,v]:=a[u-1,v-1]-(x[u-2,v-2]+x[u-2,v-1]+x[u-2,v]+
x[u-1,v-2] +x[u-1,v]+
x[u,v-2] +x[u,v-1]);
IF (x[u,v]<0) OR (x[u,v]>1) THEN exit;
END;
IF a[u-1,N]<>x[u-2,N-1]+x[u-2,N]+x[u-1,N-1]+x[u,N-1]+x[u,N] THEN exit;
IF u=M THEN
BEGIN
FOR v:=2 TO N DO
BEGIN
x[M+1,v]:=a[M,v-1]-(x[M-1,v-2]+x[M-1,v-1]+x[M-1,v]+
x[M,v-2] +x[M,v]+
x[M+1,v-2]+x[M+1,v-1]);
IF x[M+1,v]<>0 THEN exit;
END;
END;
CNDong:=TRUE;
END;
PROCEDURE ThuDong(k: INTEGER);
VAR j: INTEGER;
BEGIN
IF k>M THEN
BEGIN
Good:=TRUE;
exit;
END;
FOR j:=0 TO 1 DO
BEGIN
x[k,1]:=j;
IF CNDong(k) THEN ThuDong(k+1);
IF Good THEN exit;
END;
END;
PROCEDURE Thu3(k: INTEGER);
VAR t: INTEGER;
BEGIN
IF k>N THEN
BEGIN
ThuDong(3);
exit;
END;
t:=a[1,k-1]-(x[1,k-2]+x[2,k-2]+x[2,k-1]);
CASE t OF
0: BEGIN
x[1,k]:=0; x[2,k]:=0;
Thu3(k+1);
IF Good THEN exit;
END;
1: BEGIN
x[1,k]:=1; x[2,k]:=0;
Thu3(k+1);
IF Good THEN exit;
x[1,k]:=0; x[2,k]:=1;
Thu3(k+1);
IF Good THEN exit;
END;
2: BEGIN
x[1,k]:=1; x[2,k]:=1;
Thu3(k+1);
IF Good THEN exit;
END;
END;
END;
PROCEDURE Duyet3;
BEGIN
Good:=FALSE;
fillchar(x,sizeof(x),0);
FOR x[1,1]:=0 TO 1 DO
FOR x[2,1]:=0 TO 1 DO
BEGIN
Thu3(2);
IF Good THEN exit;
END;
END;
PROCEDURE Inkq;
VAR i,j: INTEGER;
BEGIN
IF NOT Good THEN
BEGIN
writeln(fo,'NO');
exit;
END;
writeln(fo,'YES');
FOR i:=1 TO M DO
BEGIN
FOR j:=1 TO N DO write(fo,x[i,j],' ');
writeln(fo);
END;
END;
BEGIN
assign(fi,tfi); reset(fi);
assign(fo,tfo); rewrite(fo);
Docdl;
CASE m OF
1: Duyet1;
2: Duyet2;
ELSE Duyet3;
END;
Inkq;
close(fi); close(fo);
END.
Bạn đang đọc truyện trên: AzTruyen.Top