# UVa225 Golygons

## 思路

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

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.`

## 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.