Координаты картофелин Опции

[Merhaba]

Добрый Вечер!!!
Помогите Пожалуйста решить задачу, очень надо!!!
Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

Анка и Петька ждали Чапаева и ели картошку. Вскоре они наелись и решили поиграть в «Чапаева» оставшимися четырьмя картофелинами.
Петька достал доску размером 20 × 20 клеток, положил на неё картофелины и сказал, что по правилам никакие две картофелины не могут находиться в одной клетке, а одной картофелиной можно сбить другую только в том случае, если они расположены на одной горизонтали или вертикали и между ними нет других картофелин.
Анка предложила взять некоторые картофелины и поставить их на другие свободные клетки так, чтобы каждой картофелиной можно было сбить ровно одну другую. Помогите Петьке переставить как можно меньше картофелин, чтобы выполнить её просьбу.
Исходные данные
В четырёх строках записаны координаты картофелин xi, yi — целые числа в пределах от 1 до 20. Никакие две картофелины не расположены в одной клетке.
Результат
Выведите новые координаты картофелин. Картофелины следует описывать в том же порядке, в котором они заданы на входе. Если возможных ответов несколько, выведите любой.

Пример:
1 1
2 2
4 4
4 3
Результат:
1 2
2 2
4 4
4 3

[Unconnected]

Не знаю, нужно ли ещё, но вот (экзамены на носу, времени мало, да и не получалось поначалу..).
Тут типа полный перебор, с отбором лучшего положения (страшноват, правда(очень)). Делаются лишние действия, но вроде работает.

{$APPTYPE CONSOLE}

const c=4;mp=20;
type TBin=0..1;
type TPotate=record
  x,y,b:byte;
end;

var
  i,j,xx,yy,n:byte;
  z:integer;
  m:array[1..mp,1..mp] of TBin;
  p,br:array[1..c] of TPotate;

function bcount(p,k:byte):byte;
var d,e:byte;
begin
  result:=0;e:=0;
  for d:=1 to mp do
    if (m[p,d]=1) then if (d<>k) then begin
      inc(result);inc(e);
    end else begin
      if e>1 then begin
        dec(result,e-1);e:=0;
      end;e:=0;
    end;
  if e>1 then dec(result,e-1);e:=0;
  for d:=1 to mp do
    if (m[d,k]=1) then if (d<>p) then begin
      inc(result);inc(e);
    end else begin
      if e>1 then begin
        dec(result,e-1);e:=0;
      end;e:=0;
    end;
  if e>1 then dec(result,e-1);
end;

function chOk:boolean;
begin
  result:=true;
  for xx:=1 to mp do
    for yy:=1 to mp do if (m[xx,yy]=1) and (bcount(xx,yy)<>1) then begin
      result:=false;break;
    end;
end;

Procedure PCount;
var r,t,u:byte;
begin
  u:=1;
  for r:=1 to mp do
    for t:=1 to mp do begin
      if m[r,t]=1 then with p[u] do begin
        x:=r;y:=t;b:=bcount(x,y);inc(u);
      end;
    end;
end;


Procedure wou;
begin
  for i:=1 to mp do begin
    for j:=1 to mp do write(m[i,j]);
    writeln;
  end;writeln;readln;
end;

Procedure toex;
begin
  fillchar(m,sizeof(m),0);
  for i:=1 to c do with p[i] do m[x,y]:=1;
  wou;
end;

Procedure rec(h:byte);
var d,f,t,l,xb,yb:byte;
begin
  if (h=c+1) then begin
    l:=0;inc(z);
    for d:=1 to mp do
      for f:=1 to mp do if m[d,f]=1 then begin
        for t:=1 to c do if ((br[t].x=d) and (br[t].y=f)) then inc(l);
      end;
    l:=c-l;
    if chOk then begin
      if l<n then begin
        n:=l;
        pcount;
        if n=1 then toex;
        if z>mp*mp then if n=2 then toex;
      end;
    end;
  end else begin
    xb:=p[h].x;yb:=p[h].y;
    for d:=1 to mp do begin
      for f:=1 to mp do begin
        if (m[d,f]=0) or ((d=xb) and (f=yb)) then begin
          m[d,f]:=1;
          if not((d=xb) and (f=yb)) then m[xb,yb]:=0;
          rec(h+1);
          m[d,f]:=0;
          m[xb,yb]:=1;
        end;
      end;
    end;
  end;
end;

begin
  fillchar(m,sizeof(m),0);
  for i:=1 to c do begin
    read(xx,yy);m[xx,yy]:=1;
  end;writeln;
  PCount;
  wou;
  n:=c;br:=p;z:=0;
  rec(1);
  toex;
end.

Что интересно, процедура вывода матрицы изначально называлась wout; , что, наверное, является каким-то служебным словом.. факт в том, что readln; после последнего wout-а не останавливал прогу. Пришлось переименовать)
И да, мне кажется в таких задачах лучше перебор (хоть и с оптимизациями возможными, отсечениями), чем думать что-то типа "таак, оптимальная ситуация это когда в одной грядке 2 картошки, и переставим ещё одну, тогда..."..., короче, пытаться сделать однопроходно. Ибо задача может трансформироваться в пересадку 5 картошек, и тогда думать придется заново)

Сообщение отредактировано: Unconnected - 21.05.2011 15:50

[Merhaba]

Не знаю, нужно ли ещё, но вот (экзамены на носу, времени мало, да и не получалось поначалу..).
Тут типа полный перебор, с отбором лучшего положения (страшноват, правда(очень)). Делаются лишние действия, но вроде работает.

Спасибо Вам Большое за помощь!!! попробовал закинуть на контест, выдало ошибку: ТаймЛимит на 1-ом тесте. Как можно оптимизировать код, чтобы уложится в 0,5 секунды?

Сообщение отредактировано: Merhaba - 21.05.2011 19:49