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. | помогите привести задачу к более рациональному виду) третий день сижу)) |