POJ2329 Nearest number - 2-Dp 역겨운 문제

6181 단어 number
왼쪽에서, 오른쪽에서, 왼쪽에서, 오른쪽에서부터 네 가지 순서로 Dp를 기록하고 경로를 기록한다. 최소 경로가 유일하지 않으면 이 점의 권한은 0이다.
세심함과 인내심을 극도로 고찰했지만 데이터는 비교적 약했다.
코드:
program poj2329;

const

	maxn=205;

var

	i,j,m,p,q,n					:longint;

	map,f,dp					:array[0..maxn,0..maxn]of longint;

	rec,g						:array[0..maxn,0..maxn]of record x,y:longint;end;

	

function min(i,j:longint):longint;

begin

	if i<j then exit(i);exit(j);

end;

	

begin

	readln(n);

	for i:=1 to n do for j:=1 to n do read(map[i,j]);

	fillchar(dp,sizeof(dp),127);

	for i:=1 to n do

		for j:=1 to n do

			if map[i,j]<>0 then

				begin

					dp[i,j]:=0;

					rec[i,j].x:=i;

					rec[i,j].y:=j;

				end else

				begin

					dp[i,j]:=min(dp[i,j-1],dp[i-1,j])+1;

					if dp[i,j]<maxint then

						begin

							if dp[i,j-1]=dp[i-1,j] then

								begin

									if (rec[i,j-1].x=rec[i-1,j].x)and(rec[i,j-1].y=rec[i-1,j].y) then

										rec[i,j]:=rec[i,j-1] else

											begin

												rec[i,j].x:=i;

												rec[i,j].y:=j;

											end;

								end else if dp[i,j-1]<dp[i-1,j] then

									begin

										if (map[i,j-1]=0)and(rec[i,j-1].x=i)and(rec[i,j-1].y=j-1) then

											begin

												rec[i,j].x:=i;rec[i,j].y:=j;

											end else rec[i,j]:=rec[i,j-1];

									end else

										begin

											if (map[i-1,j]=0)and(rec[i-1,j].x=i-1)and(rec[i-1,j].y=j) then

												begin

													rec[i,j].x:=i;rec[i,j].y:=j;

												end else rec[i,j]:=rec[i-1,j];

										end;

						end;

				end;

	fillchar(f,sizeof(f),127);

	for i:=1 to n do

		for j:=1 to n do

			begin

				g[i,j].x:=0;g[i,j].y:=0;

			end;

	for i:=1 to n do

		for j:=n downto 1 do

			if map[i,j]<>0 then

				begin

					f[i,j]:=0;

					g[i,j].x:=i;

					g[i,j].y:=j;

				end else

				begin

					f[i,j]:=min(f[i,j+1],f[i-1,j])+1;

					if f[i,j]<maxint then

						begin

							if f[i,j+1]=f[i-1,j] then

								begin

									if (g[i,j+1].x=g[i-1,j].x)and(g[i,j+1].y=g[i-1,j].y) then

										g[i,j]:=g[i,j+1] else

											begin

												g[i,j].x:=i;

												g[i,j].y:=j;

											end;

								end else if f[i,j+1]<f[i-1,j] then

									begin

										if (map[i,j+1]=0)and(g[i,j+1].x=i)and(g[i,j+1].y=j+1) then

											begin

												g[i,j].x:=i;g[i,j].y:=j;

											end else g[i,j]:=g[i,j+1];

									end else

										begin

											if (map[i-1,j]=0)and(g[i-1,j].x=i-1)and(g[i-1,j].y=j) then

												begin

													g[i,j].x:=i;g[i,j].y:=j;

												end else g[i,j]:=g[i-1,j];

										end;

						end;

					if f[i,j]<dp[i,j] then

						begin

							dp[i,j]:=f[i,j];

							rec[i,j]:=g[i,j];

						end else if f[i,j]=dp[i,j] then

							begin

								if (rec[i,j].x=0)and(rec[i,j].y=0)then rec[i,j]:=g[i,j];

								if ((g[i,j].x<>rec[i,j].x)or(g[i,j].y<>rec[i,j].y))and((g[i,j].x<>0)or(g[i,j].y<>0)) then

									begin

										rec[i,j].x:=i;rec[i,j].y:=j;

									end;

							end;

				end;

	fillchar(f,sizeof(f),127);

	for i:=1 to n do

		for j:=1 to n do

			begin

				g[i,j].x:=0;g[i,j].y:=0;

			end;

	for i:=n downto 1 do

		for j:=n downto 1 do

			if map[i,j]<>0 then

				begin

					f[i,j]:=0;

					g[i,j].x:=i;

					g[i,j].y:=j;

				end else

				begin

					f[i,j]:=min(f[i,j+1],f[i+1,j])+1;

					if f[i,j]<maxint then

						begin

							if f[i,j+1]=f[i+1,j] then

								begin

									if (g[i,j+1].x=g[i+1,j].x)and(g[i,j+1].y=g[i+1,j].y) then

										g[i,j]:=g[i,j+1] else

											begin

												g[i,j].x:=i;

												g[i,j].y:=j;

											end;

								end else if f[i,j+1]<f[i+1,j] then

									begin

										if (map[i,j+1]=0)and(g[i,j+1].x=i)and(g[i,j+1].y=j+1) then

											begin

												g[i,j].x:=i;g[i,j].y:=j;

											end else g[i,j]:=g[i,j+1];

									end else

										begin

											if (map[i+1,j]=0)and(g[i+1,j].x=i+1)and(g[i+1,j].y=j) then

												begin

													g[i,j].x:=i;g[i,j].y:=j;

												end else g[i,j]:=g[i+1,j];

										end;

						end;

					if f[i,j]<dp[i,j] then

						begin

							dp[i,j]:=f[i,j];

							rec[i,j]:=g[i,j];

						end else if f[i,j]=dp[i,j] then

							begin

								if (rec[i,j].x=0)and(rec[i,j].y=0)then rec[i,j]:=g[i,j];

								if ((g[i,j].x<>rec[i,j].x)or(g[i,j].y<>rec[i,j].y))and((g[i,j].x<>0)or(g[i,j].y<>0)) then

									begin

										rec[i,j].x:=i;rec[i,j].y:=j;

									end;

							end;

				end;

	for i:=1 to n do

		for j:=1 to n do

			begin

				g[i,j].x:=0;g[i,j].y:=0;

			end;

	fillchar(f,sizeof(f),127);

	for i:=n downto 1 do

		for j:=1 to n do

			if map[i,j]<>0 then

				begin

					f[i,j]:=0;

					g[i,j].x:=i;

					g[i,j].y:=j;

				end else

				begin

					f[i,j]:=min(f[i,j-1],f[i+1,j])+1;

					if f[i,j]<maxint then

						begin

							if f[i,j-1]=f[i+1,j] then

								begin

									if (g[i,j-1].x=g[i+1,j].x)and(g[i,j-1].y=g[i+1,j].y) then

										g[i,j]:=g[i,j-1] else

											begin

												g[i,j].x:=i;

												g[i,j].y:=j;

											end;

								end else if f[i,j-1]<f[i+1,j] then

									begin

										if (map[i,j-1]=0)and(g[i,j-1].x=i)and(g[i,j-1].y=j-1) then

											begin

												g[i,j].x:=i;g[i,j].y:=j;

											end else g[i,j]:=g[i,j-1];

									end else

										begin

											if (map[i+1,j]=0)and(g[i+1,j].x=i+1)and(g[i+1,j].y=j) then

												begin

													g[i,j].x:=i;g[i,j].y:=j;

												end else g[i,j]:=g[i+1,j];

										end;

						end;

					if f[i,j]<dp[i,j] then

						begin

							dp[i,j]:=f[i,j];

							rec[i,j]:=g[i,j];

						end else if f[i,j]=dp[i,j] then

							begin

								if (rec[i,j].x=0)and(rec[i,j].y=0)then rec[i,j]:=g[i,j];

								if ((g[i,j].x<>rec[i,j].x)or(g[i,j].y<>rec[i,j].y))and((g[i,j].x<>0)or(g[i,j].y<>0)) then

									begin

										rec[i,j].x:=i;rec[i,j].y:=j;

									end;

							end;

				end;

	for i:=1 to n do

		begin

			for j:=1 to n-1 do

				write(map[rec[i,j].x,rec[i,j].y],' ');

			writeln(map[rec[i,n].x,rec[i,n].y]);

		end;

end.

좋은 웹페이지 즐겨찾기