program soitario;
uses Math;
var N,M,i,j, soluzione, con_x, senza_x, nuovariga, nuovacolonna:longint;
griglia:array[0..12,0..12] of longint;
function gioca(r, c: longint): boolean;
begin
(*tris orizzontale*)
if (c-2>=0) and (griglia[r][c-2]=1) and (griglia[r][c-1]=1) then gioca:=false
(*tris orizzontale*)
else if (r-2>=0) and (griglia[r-2][c]=1) and (griglia[r-1][c]=1) then gioca:=false
(* Tris diagonale in alto a sx*)
else if (r-2>=0 ) and (c-2>=0) and (griglia[r-2][c-2]=1) and (griglia[r-1][c-1]=1) then gioca:=false
(* Tris diagonale in alto a dx*)
else if (r-2>=0) and (c+2<=M) and (griglia[r-2][c+2]=1) and (griglia[r-1][c+1]=1) then gioca:=false
else gioca := true;
end;
function riempi (riga, colonna:longint):longint;
begin
if riga>=N then begin soluzione:=0; exit; end
else
begin
if griglia[riga,colonna]<>-1 then begin soluzione:=griglia[riga,colonna]; end
else
begin
if colonna+1=M then nuovariga:=riga+1
else nuovariga:=riga;
nuovacolonna:= (colonna+1) mod M;
(* Non metto la X*)
senza_x:= riempi(nuovariga,nuovacolonna); con_x:=0;
(*Se posso, metto la X*)
if gioca (riga,colonna)=true then
begin
if colonna+1=M then nuovariga:=riga+1
else nuovariga:=riga;
nuovacolonna:= (colonna+1) mod M;
griglia[nuovariga][nuovacolonna]:=1;
con_x:= 1 + Riempi(nuovariga,nuovacolonna);
for i:=1 to N do begin
for j:=1 to M do write(griglia[i,j],' '); writeln; end; writeln;
(* Reset della griglia[riga][col]*)
griglia[riga][colonna]:=-1;
end;
(*Ritorno la soluzione migliore*)
end;
griglia[riga][colonna]:= max(senza_x,con_x);
soluzione:=griglia[riga, colonna];
end;
riempi:=soluzione;
end;
begin
readln(N,M);
for i:=0 to N do
for j:=0 to M do griglia[i,j]:=-1;
con_x:= 0;
writeln(riempi(0 , 0));
end.
cHJvZ3JhbSBzb2l0YXJpbzsKdXNlcyBNYXRoOwp2YXIgTixNLGksaiwgc29sdXppb25lLCBjb25feCwgc2VuemFfeCwgbnVvdmFyaWdhLCBudW92YWNvbG9ubmE6bG9uZ2ludDsKICAgIGdyaWdsaWE6YXJyYXlbMC4uMTIsMC4uMTJdIG9mIGxvbmdpbnQ7CiAgICAKZnVuY3Rpb24gZ2lvY2EociwgYzogbG9uZ2ludCk6IGJvb2xlYW47CmJlZ2luCiAgICAgICgqdHJpcyBvcml6em9udGFsZSopCiAgIGlmIChjLTI+PTApIGFuZCAoZ3JpZ2xpYVtyXVtjLTJdPTEpIGFuZCAoZ3JpZ2xpYVtyXVtjLTFdPTEpIHRoZW4gZ2lvY2E6PWZhbHNlCiAgICAgICgqdHJpcyBvcml6em9udGFsZSopCiAgICAgIGVsc2UgIGlmIChyLTI+PTApIGFuZCAoZ3JpZ2xpYVtyLTJdW2NdPTEpIGFuZCAoZ3JpZ2xpYVtyLTFdW2NdPTEpIHRoZW4gZ2lvY2E6PWZhbHNlCiAgICAoKiBUcmlzIGRpYWdvbmFsZSBpbiBhbHRvIGEgc3gqKQogICAgICBlbHNlIGlmIChyLTI+PTAgKSBhbmQgKGMtMj49MCkgYW5kIChncmlnbGlhW3ItMl1bYy0yXT0xKSBhbmQgKGdyaWdsaWFbci0xXVtjLTFdPTEpIHRoZW4gZ2lvY2E6PWZhbHNlCiAgICAoKiBUcmlzIGRpYWdvbmFsZSBpbiBhbHRvIGEgZHgqKQogICAgICBlbHNlIGlmIChyLTI+PTApIGFuZCAoYysyPD1NKSBhbmQgKGdyaWdsaWFbci0yXVtjKzJdPTEpIGFuZCAoZ3JpZ2xpYVtyLTFdW2MrMV09MSkgdGhlbiBnaW9jYTo9ZmFsc2UKICAgICAgICAgIGVsc2UgICBnaW9jYSA6PSB0cnVlOwplbmQ7ICAgIApmdW5jdGlvbiByaWVtcGkgKHJpZ2EsIGNvbG9ubmE6bG9uZ2ludCk6bG9uZ2ludDsKICBiZWdpbgogICAgaWYgcmlnYT49TiB0aGVuICBiZWdpbiBzb2x1emlvbmU6PTA7IGV4aXQ7IGVuZAogICAgICAgICAgICAgICAgICAgZWxzZSAKICAgICAgICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgICAgaWYgZ3JpZ2xpYVtyaWdhLGNvbG9ubmFdPD4tMSB0aGVuIGJlZ2luIHNvbHV6aW9uZTo9Z3JpZ2xpYVtyaWdhLGNvbG9ubmFdOyAgZW5kCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgY29sb25uYSsxPU0gdGhlbiBudW92YXJpZ2E6PXJpZ2ErMQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UgbnVvdmFyaWdhOj1yaWdhOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG51b3ZhY29sb25uYTo9IChjb2xvbm5hKzEpIG1vZCBNOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICgqIE5vbiBtZXR0byBsYSBYKikKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZW56YV94Oj0gcmllbXBpKG51b3ZhcmlnYSxudW92YWNvbG9ubmEpOyBjb25feDo9MDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKlNlIHBvc3NvLCBtZXR0byBsYSBYKikKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiBnaW9jYSAocmlnYSxjb2xvbm5hKT10cnVlIHRoZW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiZWdpbiAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgY29sb25uYSsxPU0gdGhlbiBudW92YXJpZ2E6PXJpZ2ErMQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZSBudW92YXJpZ2E6PXJpZ2E7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG51b3ZhY29sb25uYTo9IChjb2xvbm5hKzEpIG1vZCBNOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBncmlnbGlhW251b3ZhcmlnYV1bbnVvdmFjb2xvbm5hXTo9MTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29uX3g6PSAxICsgUmllbXBpKG51b3ZhcmlnYSxudW92YWNvbG9ubmEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgaTo9MSB0byBOIGRvIGJlZ2luCgkgICAgICAgICAgICBmb3Igajo9MSB0byBNIGRvIHdyaXRlKGdyaWdsaWFbaSxqXSwnICcpOyB3cml0ZWxuOyBlbmQ7IHdyaXRlbG47CgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKiBSZXNldCBkZWxsYSBncmlnbGlhW3JpZ2FdW2NvbF0qKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBncmlnbGlhW3JpZ2FdW2NvbG9ubmFdOj0tMTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKCpSaXRvcm5vIGxhIHNvbHV6aW9uZSBtaWdsaW9yZSopCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JpZ2xpYVtyaWdhXVtjb2xvbm5hXTo9IG1heChzZW56YV94LGNvbl94KTsgCiAgICAgICAgICAgICAgICAgICAgICAgc29sdXppb25lOj1ncmlnbGlhW3JpZ2EsIGNvbG9ubmFdOyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgIHJpZW1waTo9c29sdXppb25lOyAgICAgIAplbmQ7ICAgICAgICAgICAgICAgICAgIApiZWdpbgoJcmVhZGxuKE4sTSk7Cglmb3IgaTo9MCB0byBOIGRvCgkgICAgICAgICAgICBmb3Igajo9MCB0byBNIGRvIGdyaWdsaWFbaSxqXTo9LTE7CgkgICAgICAgY29uX3g6PSAwOwoJd3JpdGVsbihyaWVtcGkoMCAsIDApKTsKZW5kLgoK