UVa225 Golygons

链接：Link 耗时：0.699s

思路

dfs(t, x, y, d, s)表示当前走了t步，在(x,y)，上一个方向为d，s为一个求和用的辅助变量。 当前位置无法走完剩下的路时直接回溯。可节省接近2s的时间。 ps: 这道题虽然没有明说每个城市只走一次，但它的确那样判了，这一点坑了我好久。

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.