|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 30 Mar 2002 11:51:38
To : Sergey Prohorenko
Subject : несложная задачка, а поди ж ты ...
--------------------------------------------------------------------------------
28 Мар 02 19:03, you wrote to all:
SP> Есть матрица N*N, заполненная 0 и 1. Известно, что есть такое i, что
SP> i-тый столбец состоит из "0", а i-я строка - из "1" (что стоит на
SP> пересечении - неизвестно). Hужно найти это i за кол-во операций O(N).
Вот подумал, и что-то придумал:
Суть следующая: берём угол, проверяем граничный крест, если по краям не нули,
значит это не та строка, если по вертикали не 1 значит не тот столбец, и
сдвигаемся вниз и вправо если надо. Знаком '-' и '+' отмечен путь, где + - там
граничные условия удовлетворяют. Как только дошли до того места где попали
граничные условия - переходим на следующую строку и повторяем с первого столбца.
потом также для столбцов.
-0 1 0 1 1
0-1-0 1 1
0 0 0+0 0
-1-0 1 1 0
0 0-0 1 1
-0 1 0 1-1
0-1-0 1-1
0 0 0+0 0
1 0 1 1 0
0 0 0 1 1
Hюхом чую что где-то её подловить можно, я не все тесты проверил, только нет
большого желания все баги искать, ИМХО идея что-то стоит, надо только немного
обработать её. Алгоритм получается где-то 4n*<проверки>.
Возможные ошибки - когда много точек удовлетворяют граничным решениям,
возможные пути выхода - там где стоит '-' - ни строка не столбец не
удовлетворяет, первый проход выявляет все неудовлетворяющие строки, второй
проход все неудовлетворяющие столбцы, и возможно недопроверенные могут быть
только столбцы с нормальными граничными условиями.
uses Crt;
var a,b1,b2:Array[0..50,0..50] of byte;
a1,a2:Array[0..50] of byte;
n,i,j,di,dj:Integer;
f:Text;
procedure Draw;
var i,j:Integer;
const s:String[7]='-+ ';
begin ClrScr;
for i:=1 to n do
begin
for j:=1 to n do
begin TextColor(b1[i,j]); Write(s[b1[i,j]],a[i,j]); end;
WriteLn;
end;
WriteLn;
for i:=1 to n do
begin
for j:=1 to n do
begin TextColor(b2[i,j]); Write(s[b2[i,j]],a[i,j]); end;
WriteLn;
end;
ReadKey;
end;
begin
FillChar(a,SizeOf(a),0);
FillChar(b1,SizeOf(b1),7);FillChar(b2,SizeOf(b2),7);
FillChar(a1,SizeOf(a1),0);FillChar(a2,SizeOf(a2),0);
Assign(f,'input.txt');Reset(f);
ReadLn(f,n);
for i:=1 to n do
for j:=1 to n do
begin
read(f,a[i,j]);
if i=1 then a[n+1,j]:=a[i,j];
if j=1 then a[i,n+1]:=a[i,j];
if i=n then a[0,j]:=a[i,j];
if j=n then a[i,0]:=a[i,j];
end;
FillChar(a1,SizeOf(a1),0); FillChar(a2,SizeOf(a2),0);
i:=1;j:=1;
while (i<=n) and (j<=n) do
begin di:=1;dj:=1;
while (i<=n) and (j<=n)and((di<>0)or(dj<>0)) do
begin b1[i,j]:=1;
if (a[i-1,j]<>1)or(a[i+1,j]<>1) then dj:=1 else dj:=0;
if (a[i,j-1]<>0)or(a[i,j+1]<>0) then di:=1 else di:=0;
a1[i]:=di;a2[j]:=dj;inc(i,di);inc(j,dj);b1[i,j]:=2;
Draw;
end;
if i<n then
begin inc(i);j:=1; end
end;
i:=1;j:=1;
while (i<=n) and (j<=n) do
begin di:=1;dj:=1;
while (i<=n) and (j<=n)and((di<>0)or(dj<>0)) do
begin b2[i,j]:=1;
if (a[i-1,j]<>1)or(a[i+1,j]<>1) then dj:=1 else dj:=0;
if (a[i,j-1]<>0)or(a[i,j+1]<>0) then di:=1 else di:=0;
a1[i]:=di;a2[j]:=dj;inc(i,di);inc(j,dj);b2[i,j]:=2;
Draw;
end;
if j<n then
begin inc(j);i:=1; end
end;
Close(f);
end.
Andrey
... Сколько волка не корми, а у слона все равно больше!
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
несложная задачка, а поди ж ты ... 
