ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1497. Разрезание квадрата

WA #9
Послано Thunder 6 апр 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. ^_^