UVa225 Golygons

链接:Link 耗时:0.699s

思路

dfs(t, x, y, d, s) 表示当前走了 t 步,在 (x,y),上一个方向为 d,s 为一个求和用的辅助变量。

当前位置无法走完剩下的路时直接回溯。可节省接近 2s 的时间。

p.s. 这道题虽然没有明说每个城市只走一次,但它的确那样判了,这一点坑了我好久。

Code

//Accepted.
const
dx: array [1..4] of integer = (1, 0, 0, -1);
dy: array [1..4] of integer = (0, 1, -1, 0);
dir: array [1..4] of char = ('e', 'n', 's', 'w');

var
a: array [1..50, 1..2] of integer; //障碍物
k, i, n, _, x, y: integer;
ans: array [1..20] of char;
tot: longint;
vis: array [-220..220, -220..220] of boolean;

function judge(x1, y1, x2, y2: longint): Boolean; //判断刚刚走过的路上是否有障碍物
var
i: Integer;
begin
judge := False;
if x1 = x2 then
begin
for i := 1 to k do
if (a[i, 1] = x1) and ((a[i, 2] - y1)*(a[i, 2] - y2) <= 0) then exit;
end
else
for i := 1 to k do
if (a[i, 2] = y2) and ((a[i, 1] - x1)*(a[i, 1] - x2) <= 0) then exit;
judge := True;
end;

procedure print;
var
i: Integer;
begin
for i := 1 to n do write(ans[i]);
writeln;
inc(tot);
end;

procedure dfs(t, x, y, d, s: integer);
var
i, sum: Integer;
tx, ty: longint;
begin
if t = n then
begin
if (x = 0) and (y = 0) then print;
exit;
end;

sum := s - t - 1;
inc(t);

for i := 1 to 4 do
begin
if (i = d) or (i + d = 5) then continue; //方向相同或相反
tx := x + dx[i] * t;
ty := y + dy[i] * t;
if vis[tx, ty] then continue; //走过
if abs(tx) + abs(ty) > sum then continue; //回不去,剪枝
if not judge(x, y, tx, ty) then continue; //有障碍物
ans[t] := dir[i];
vis[tx, ty] := True;
dfs(t, tx, ty, i, sum);
vis[tx, ty] := False;
end;
end;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(_);
while _ > 0 do
begin
dec(_);
read(n, k);
fillchar(vis, sizeof(vis), 0);
for i := 1 to k do
read(a[i, 1], a[i, 2]);
fillchar(ans, sizeof(ans), 0);
tot := 0;
dfs(0, 0, 0, -1, n * (n+1) div 2);
writeln('Found ', tot, ' golygon(s).');
writeln;
end;

close(input); close(output);
end.

作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。

«UVa817 According to Bartjens

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.