I am not Liar
Junior Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Вопрос по задаче:
[box]
На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений "вправо", "вверх", "влево" или "вниз".
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Формат входных данных
Во входном файле заданы сначала размеры поля - число строк N и число столбцов M (1 меньше или равно N меньше или равно 1000, 1 меньше или равно M меньше или равно 1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 - вверх, 3 - влево, 4 - вниз. Числа в строке разделяются пробелами.
Формат выходных данных
В выходной файл выведите одно число - количество клеток, начав с которых фишка никогда не покинет пределы поля.
[/box]
вопрос: как рациональнее реализовать динамику?
вот мое корявое решение:
Код:
var p,p1:array[1..1000,1..1000] of shortint;
i,j,all:integer;
m,n:longint;
res:integer;
procedure go_go_go(x,y:integer);
var r,o,k:integer;
begin
r:=0;
if (p1[x,y]<>res) and (p1[x,y]<>1) then begin
repeat
p1[x,y]:=res;
if p[x,y]=1 then go_go_go(x,y+1);
if p[x,y]=2 then go_go_go(x-1,y);
if p[x,y]=3 then go_go_go(x,y-1);
if p[x,y]=4 then go_go_go(x+1,y);
until (p1[x,y]=1) or (p1[x,y]=res);
end;
if p1[x,y]=1 then r:=3;
if p1[x,y]=res then r:=2;
for o:=1 to m do begin
for k:=1 to n do begin
if p1[o,k]=res then begin
if r=3 then p1[o,k]:=1;
end;
end;
end;
end;
procedure init;
var all:longint;
begin
assign(input,'e.in');
reset(input);
assign(output,'e.out');
rewrite(output);
readln(m,n);
for i:=1 to m do begin
for j:=1 to n do read(p[i,j]);
readln;
end;
for i:=1 to n do begin
if p[1,i]=2 then p1[1,i]:=1;
if p[m,i]=4 then p1[m,i]:=1;
end;
for i:=1 to m do begin
if p[i,1]=3 then p1[i,1]:=1;
if p[i,n]=1 then p1[i,n]:=1;
end;
end;
begin
init;
for i:=1 to m do begin
for j:=1 to n do begin
if p1[i,j]=0 then begin
res:=res-1;
go_go_go(i,j);
end;
end;
end;
all:=0;
for i:=1 to m do begin
for j:=1 to n do begin
if p1[i,j]=1 then inc(all);
end;
end;
all:=m*n-all;
writeln(all);
end.
|
проходит 6 из 25, остальные по ограничению по времени или по памяти не проходит.
сделал еще одно решение, корявое до ужаса, но проходит 21 из 25, в 4 случаях ответ неправильный.
Код:
var p,p1:array[1..1000,1..1000] of byte;
m,n:integer;
procedure init;
var i,j,i1,j1:integer;
var all:longint;
begin
assign(input,'e.in');
reset(input);
assign(output,'e.out');
rewrite(output);
readln(m,n);
for i:=1 to m do begin
for j:=1 to n do read(p[i,j]);
readln;
end;
for i:=1 to n do begin
if p[1,i]=2 then p1[1,i]:=1;
if p[m,i]=4 then p1[m,i]:=1;
end;
for i:=1 to m do begin
if p[i,1]=3 then p1[i,1]:=1;
if p[i,n]=1 then p1[i,n]:=1;
end;
{гыгы, вот этот цикл походу все портит =) 25 раз если поставить пройдет 21 тест, меньше поставить - меньше пройдет  }
for i1:=1 to 25 do begin
//конец тупой строчки)
for i:=1 to m do begin
for j:=1 to n do begin
if p1[i,j]=0 then begin
if p[i,j]=1 then begin
if p1[i,j+1]=1 then p1[i,j]:=1;
end;
if p[i,j]=2 then begin
if p1[i-1,j]=1 then p1[i,j]:=1;
end;
if p[i,j]=3 then begin
if p1[i,j-1]=1 then p1[i,j]:=1;
end;
if p[i,j]=4 then begin
if p1[i+1,j]=1 then p1[i,j]:=1;
end;
end;
end;
end;
end;
all:=0;
for i:=1 to m do begin
for j:=1 to n do begin
if p1[i,j]=1 then inc(all);
end;
end;
all:=m*n-all;
write(all);
end;
begin
init;
end.
|
помогите привести задачу к более рациональному виду) третий день сижу)) |
