ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1497. Cutting a Square

WA #9
Posted by Thunder 6 Apr 2007 15:38
Can anybody help me? I have WA on the test number 9, but I don't know where I have errors in code. I think, my algorithm is true. It work on all my tests, but crash on jury test. Find errors in my code or give me that test, please. He is it:

program Sum_1497;

{$APPTYPE CONSOLE}
var
  a,b,c,d,e,f,g,h,i,j,n:integer;
  q:array[1..1000,1..1000]of integer;
  ch:char;
  x1,x2,y1,y2:integer;

function TestRect(x1,y1,x2,y2,f:integer):boolean;
var
  i,j:integer;
  a:boolean;
  x,y:integer;
begin
  a:=true;

  if f=1 then
    for j:=y1 to y2 do
    begin
      x:=n+1;
      y:=0;
      for i:=x1 to x2 do
      begin
        if q[j][i]=1 then
          if i<x then x:=i;
        if q[j][i]=0 then
          if i>y then y:=i;
      end;
      if x<y then
        a:=false;
  end;

  if f=2 then
    for j:=y1 to y2 do
    begin
      x:=0;
      y:=n+1;
      for i:=x1 to x2 do
      begin
        if q[j][i]=1 then
          if i>x then x:=i;
        if q[j][i]=0 then
          if i<y then y:=i;
      end;
      if x>y then
        a:=false;
  end;

  if f=3 then
    for j:=x1 to x2 do
    begin
      x:=n+1;
      y:=0;
      for i:=y1 to y2 do
      begin
        if q[i][j]=1 then
          if i<x then x:=i;
        if q[i][j]=0 then
          if i>y then y:=i;
      end;
      if x<y then
        a:=false;
  end;

  if f=4 then
    for j:=x1 to x2 do
    begin
      x:=0;
      y:=n+1;
      for i:=y1 to y2 do
      begin
        if q[i][j]=1 then
          if i>x then x:=i;
        if q[i][j]=0 then
          if i<y then y:=i;
      end;
      if x>y then
        a:=false;
  end;

  TestRect:=a;
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    for j:=1 to n do
    begin
      read(ch);
      q[i][j]:=Ord(ch)-Ord('0');
    end;
    readln;
  end;
  x1:=n+1;
  y1:=n+1;
  x2:=0;
  y2:=0;

  for i:=1 to n do
    for j:=1 to n do
    begin
      if q[i][j]=0 then
      begin
        if i>x2 then x2:=i;
        if i<x1 then x1:=i;
        if j>y2 then y2:=j;
        if j<y1 then y1:=j;
      end;
    end;

  if x1=n+1 then
  begin
    writeln('Yes');
    halt;
  end;
  if (TestRect(1,y1,x2,y2,1))or(TestRect(x1,y1,n,y2,2))
  or(TestRect(x1,1,x2,y2,3))or(TestRect(x1,y1,x2,n,4)) then
    begin
      writeln('Yes');
//      readln(a);
      halt;
    end;

  writeln('No');
//  readln(a);
end.

Comments: I find rect, in which this figure is situated. Then I test all rects, that must bu filles by "0" to free the figure. For this i find the last symbol "0" and the first symbol "1" in each line. If x (position of "0") > y(position of "1") then we cann't free the figure by this direction. There are 4 different directions: up, down, left, and right. If in any of that direction I get "true", then the answer if "Yes". Else the answer is "No".

P.S. Sorry for poor English. ^_^