用Makefile搭建博客

缘起

我几乎不会 HTML，不会使用 Perl、Python 的库，不会 PHP 和 Ruby，不懂 JavaScript，但也想搭个博客。

尝试 WordPress

首先选择的是 WordPress，基本上是照着 这篇文章 做的，在 tusooa 和 phoenixlzx 的大力帮助下，注册了个 .tk 的域名和一个免费服务器，基本上算是搭起来了。不过有些不满意的地方，最讨厌的是它不是用标记语言写的，有些繁琐。

Read More

用Expect连接无线网络

垃圾的无线网卡驱动

我的无线网卡是 Broadcom BCM57780，这个东西，Linux下的无线驱动做得非常烂。以前我用Gentoo Portage中的net-wireless/broadcom-sta，后来听 microcai 的，直接在 menuconfig 里配置。这个驱动对应的模块名称是 brcmsmac，必须编译成模块（编译进内核的话，我没成功打开无线过）。它还需要 firmware，而且路径是定死的（使用其他名称是不行的，至少我没成功）。它在 dmesg 中的信息非常简略，如果你 firmware 的路径配置错的话，每次启动有一定机率 dmesg 会提示你正确的路径（这个……）。

Read More

genkernel

第一次为gentoo编译内核，发现默认选项没有有线网络支持（没有eth0设备），也不管哪些选项是自己真正需要的，选了很多。恰好linux-2.6.34-gentoo出来了，就尝试着重新配置一下。

1
genkernel --bootloader=grub --menuconfig --no-clean all

以前不知道要用--no-clean，每次编译都要花很长时间，这个选项可以让genkernel不去执行 make clean，第二次编译花的时间就会少很多

File systems <> The Extended 4 (ext4) filesystem #我大部分分区用的是 ext4，这一项默认没有设 <> Reiserfs support #/usr/portage 下有很多目录和小文件，所以我单独挂载在一个 reiserfs 分区 -- Native language support <> Simplified Chinese charset (CP936, GB2312) <*> Traditional Chinese charset (Big5)

Executable file formats / Emulations [*] IA32 Emulation #这个好像是执行 32-bit ELF 的，否则像 firefox-bin wine 等就无法运行

我的网卡是Broadcom Corporation NetLink BCM57780 Gigabit Ethernet PCIe

1
2
3
4
5
6
Device Drivers
    Network device support
        PHY Device support and infrastructure
            [*] Drivers for Broadcom PHYs
        Ethernet (100 Mbit)
            [*] Broadcom Tigon3 support

我的framebuffer的配置：

1
emerge -av v86d
1
2
3
4
5
6
7
8
9
10
11
12
General Setup ->
    (/usr/share/v86d/initramfs) Initramfs source file(s)
Device Drivers
    <*> Connector - unified userspace <-> kernelspace linker
    Support for frame buffer devices
        [*] Enable firmware EDID
        [*] Enable Video mode handling helpers
    [ ] Enable Tile Blitting Support #选择了这一项 CONFIG_FB_CON_DECOR 选项就没有了
        [*] Userspace VESA VGA graphics support
    Console display driver support
        Framebuffer Console Support
            [*] Support for the Framebuffer Console Decorations

Awesome 3 debian menu

Awesome 3 里可以启用 debian menu，方法是新建一个带 x 属性的文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/install-menu
# this file has to be executable
# put under ~/.menu-methods
# will run by update-menus
# default generate ~/.config/awesome/menu.lua
# you need to require("menu") to use menu.debian_menu

compat="menu-1"

!include menu.h

compat="menu-2"
outputencoding= "UTF-8";

function q($s) = "\"" esc($s,"\\\"") "\"";
function s($s) = replacewith(replacewith($s,"/","_"), " ", "_");
function findicon($filename)=
       ifelsefile($filename, q($filename),
        iffile("/usr/share/pixmaps/" $filename,
                   q("/usr/share/pixmaps/" $filename)));
function x11menu()= "\t{"q(title())","q($command) ifnempty($icon, ","findicon($icon))"},\n";
function textmenu()= "\t{"q(title())", \"x-terminal-emulator -e \".."q($command) ifnempty($icon, ","findicon($icon))"},\n";

supported;
    x11= x11menu();
    text= textmenu();
endsupported;

startmenu=      s($section)" = {\n";
endmenu=        "}\n";
submenutitle=   "\t{"q(title())","s($section)"},\n";
genmenu=        "menu.lua";
rootsection=    "debian_menu";
userprefix=     "/.config/awesome/";
preoutput=      "-- automatically generated file. Do not edit (see /usr/share/doc/menu/html)\n\nmodule(\"menu\")\n\n";

放在 ~/.menu-methods下，然后运行

1
$ update-menus

这样就会在 ~/.config/awesome 下面建立 menu.lua，然后在 lua.rc 里做如下修改：

1
2
3
4
5
6
7
8
9
10
-- Load Debian menu entries
require("debian.menu")



mymainmenu = awful.menu({ items = { { "awesome", myawesomemenu, beautiful.awesome_icon },
                                    { "open terminal", terminal },
                    { "debian", debian.menu.Debian_menu.Debian }
                                  }
                        })

参考：http://awesome.naquadah.org/wiki/Awful.menu

ZJU 1638. Greedy Island 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Greedy Island
Time Limit: 5 Seconds      Memory Limit: 32768 KB
Gon and Killua are engaged in a game of Greedy Island. The goal of the game is to collect 100 spell cards distributed all over the game. A spell card has three properties: Attack, Defense and Special. The numeric value of each property is between 0 and 100. Each card can be used only ONCE. All the spell cards must be stored in the Book - the initial item of the game. The Book can store at most 50 spell cards, so Gon and Killua can have at most 100 spell cards in all. Now Gon and Killua have n spell cards, and they want to use A cards for Attack, B cards for Defense and C cards for Special uses (A + B + C <= 100). If n > A + B + C, they have to discard some cards.

They would like to know the maximum sum of the Attack value in Attack Group, Defense value in Defense Group and Special value in Special Group. If there are multiple solutions, choose the solution with the maximum sum of ALL the properties of all the cards.

Input

The first line contains an integer T (1 <= T <= 10), the number of test cases.

For each test case, the first line contains a single integer n (n <= 100,100); the next line contains three integers A, B and C (A, B, C >= 0, A + B + C <= n); the following n lines contain the Attack value, Defense value and Special value of the n spell cards.


Output

For each test case, print the maximum sum of Attack value in Attack Group, Defense value in Defense Group and Special value in Special Group, and maximum sum of ALL the properties of all the cards in one line, separated with one space.


Sample Input

2
3
1 1 1
100 0 0
0 100 0
0 0 100
4
1 1 1
12 32 44
33 48 37
37 38 33
46 79 78

Sample Output

300 300
163 429

有 n (n <= 100100) 张卡片，卡片 i 有 a_i b_i c_i 三个属性，选则不超过 A 张用于提升属性一，不超过 B 张提升属性二，不超过 C 张提升属性三，每张卡片只能用于提升一种属性。求三种属性提升值之和的最大值，若有多解，最大化 sigma(S_i)，S_i = A_i + B_i + C_i。

容易构建最大费用最大流模型，但顶点数很多，需要优化。 以 (A_i, S_i) 为关键字，保留最大的 A+B+C 张卡片 以 (B_i, S_i) 为关键字，保留最大的 A+B+C 张卡片 以 (C_i, S_i) 为关键字，保留最大的 A+B+C 张卡片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int N = 100100;
struct Card { int a, b, c, s; bool valid; } cards[N];
bool cmp_by_a(const Card &x, const Card &y) {return x.a > y.a || x.a == y.a && x.s > y.s; }
bool cmp_by_b(const Card &x, const Card &y) {return x.b > y.b || x.b == y.b && x.s > y.s; }
bool cmp_by_c(const Card &x, const Card &y) {return x.c > y.c || x.c == y.c && x.s > y.s; }

const int V = 100*3+4;
bool flag[V];
int h[V], mincost;
struct Edge {int v, c, w; Edge *next, *pair; } *e[V], pool[V*10], *pit = pool;
void insert(int u, int v, int c, int w)
{
    *pit = (Edge){v, c, w, e[u]}; e[u] = pit++;
    *pit = (Edge){u, 0, -w, e[v]}; e[v] = pit++;
    e[u]->pair = e[v];
    e[v]->pair = e[u];
}
bool relabel(int sink)
{
    int d = INT_MAX;
    for (int u = 0; u <= sink; u++) if (flag[u])
        for (Edge *it = e[u]; it; it = it->next)
            if (it->c > 0 && !flag[it->v])
                d = min(d, h[it->v]+it->w-h[u]);
    if (d == INT_MAX) return false;
    for (int u = 0; u <= sink; u++)
        if (flag[u]) h[u] += d;
    return true;
}
int augment(int u, int d, int src, int sink)
{
    if (u == sink)
        return mincost += (h[src]-h[sink])*d, d;
    flag[u] = true;
    int old = d;
    for (Edge *it = e[u]; it; it = it->next)
        if (it->c > 0 && !flag[it->v] && h[it->v]+it->w == h[u]) {
            int dd = augment(it->v, min(d, it->c), src, sink);
            it->c -= dd, it->pair->c += dd;
            if (!(d -= dd)) break;
        }
    return old-d;
}

int main()
{
    int cases, n, A, B, C;
    for (scanf("%d", &cases); cases--; ) {
        scanf("%d%d%d%d", &n, &A, &B, &C);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &cards[i].a, &cards[i].b, &cards[i].c);
            cards[i].s = cards[i].a+cards[i].b+cards[i].c;
            cards[i].valid = false;
        }

        nth_element(cards, cards+A+B+C, cards+n, cmp_by_a);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        nth_element(cards, cards+A+B+C, cards+n, cmp_by_b);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        nth_element(cards, cards+A+B+C, cards+n, cmp_by_c);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        int nn = 0;
        for (int i = 0; i < n; i++)
            if (cards[i].valid)
                cards[nn++] = cards[i];
        n = nn;

        const int sink = 4+n, tsrc = sink+1, tsink = tsrc+1;
        pit = pool;
        memset(e, 0, sizeof(e));
        mincost = 0;
        insert(0, 1, A, 0);
        insert(0, 2, B, 0);
        insert(0, 3, C, 0);
        for (int i = 0; i < n; i++) {
            const int foo = cards[i].s;
            insert(4+i, 1, 1, cards[i].a*100000+foo); mincost -= cards[i].a*100000+foo;
            insert(4+i, 2, 1, cards[i].b*100000+foo); mincost -= cards[i].b*100000+foo;
            insert(4+i, 3, 1, cards[i].c*100000+foo); mincost -= cards[i].c*100000+foo;
            insert(tsrc, 4+i, 3, 0);
            insert(4+i, sink, 1, 0);
        }
        insert(1, tsink, n, 0);
        insert(2, tsink, n, 0);
        insert(3, tsink, n, 0);
        insert(sink, 0, INT_MAX, 0);

        memset(h, 0, sizeof(h));
        do while (memset(flag, 0, sizeof(flag)), augment(tsrc, INT_MAX, tsrc, tsink));
        while (relabel(tsink));
        do while (memset(flag, 0, sizeof(flag)), augment(0, INT_MAX, 0, sink));
        while (relabel(sink));
        printf("%d %d\n", (-mincost)/100000, (-mincost)%100000);
    }
}

checker 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/env python
#
#   Copyright (C) 2010, 2011 MaskRay
#
#   This program is free software: you can redistribute it and/or modify
#   it under the terms of the GNU General Public License as published by
#   the Free Software Foundation, either version 3 of the License, or
#   (at your option) any later version.
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
#   ------------------------------------------------------------------------------
#
#   checker
#           check programs using testdata

COPYING = '''checker
Copyright (C) 2010, 2011 MaskRay
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
'''

def rreplace(s1, s2, s3):
    p = s1.rfind(s2)
    return s1[:p] + s3 + s1[p+len(s2):] if p != -1 else s1

def test(s, pat1, pat2):
    p = s.find(pat1)
    if p == -1:
        return False
    q = s.find(pat2)
    while q != -1:
        if not p <= q < p+len(pat1):
            return True
        q = s.find(pat2, q+len(pat2))
    return False

if __name__ == '__main__':

    import math, sys, os, re, subprocess, threading, time, tempfile
    from optparse import OptionParser

    def main():

        def print_copying():
            sys.stdout.write(COPYING)
            exit(0)

        usage = '''usage: %prog source [input] [output]
        source  - source file
        input   - suffix of input files (default `in')
        output  - suffix of output files (default `out')'''
        parser = OptionParser(usage=usage)
        parser.add_option('-p', '--path', action='store',
                          dest='path', default='/tmp',
                          help='specify the path of testdata')
        parser.add_option('-i', '--dataid', action='store',
                          dest='dataid', default='', help='specify the data id')
        parser.add_option('-d', '--detail', action='store_true',
                          dest='show_detail', default=False, help='show details')
        parser.add_option('-s', '--showtime', action='store_true',
                          dest='show_time', default=False, help='show time used')
        parser.add_option('-t', '--time-limit', action='store', type='float',
                          dest='time_limit', default=1.)
        parser.add_option('--version', action="callback",
                          callback=lambda o, s, v, p: print_copying(),
                          help="print the COPYING and exit")
        (options, args) = parser.parse_args()

        options.path = os.path.expanduser(options.path)
        if len(args) < 1 or len(args) > 4:
            parser.print_usage()
            sys.exit(1)
        if len(args) < 2:
            args.append('in')
        if len(args) < 3:
            args.append('out')
        r = re.compile('\d+')

        L = [file for file in os.listdir(options.path) if test(file, args[0], args[1])]
        for file in sorted(L, key = lambda x: int(r.findall(x)[-1] if
            r.findall(x) else sys.maxint)):
            if options.dataid != '' and (not r.findall(file) or
                    r.findall(file)[-1] != options.dataid):
                continue
            print('---' + file + '---')

            temp = tempfile.NamedTemporaryFile()
            sub = subprocess.Popen('./main', stdin=open(os.path.join(options.path, file)), stdout=temp)
            bgn = time.time()
            timer = threading.Timer(options.time_limit, sub.terminate)
            timer.start()
            ret = sub.wait()
            end = time.time()
            timer.cancel()

            RESET = '\033[0m'
            if ret == -11:
                print('\033[1;34m' + 'runtime error' + RESET)
            elif ret == -15:
                print('\033[1;35m' + 'time limit exceed' + RESET)
            elif ret == 0:
                sys.stdout.write('\033[1m')
                sys.stdout.flush()
                with open(os.path.join(options.path, rreplace(file, args[1], args[2]))) as f:
                    lines = f.readlines()

                if len(lines) == 1 and re.search('''\d+\.\d+''', lines[0]):
                    res = float(lines[0])
                    with open(temp.name) as f:
                        lines = f.readlines()
                    if len(lines) != 1:
                        print('wrong answer' + RESET)
                    elif math.isnan(float(lines[0])) or abs(float(lines[0])-res) > 1e-9:
                        print('< %f\n---\n> %f\n' % (res, float(lines[0])) + RESET)
                elif 0 == os.system('diff --strip-trailing-cr %s %s %s' %
                                  ('' if options.show_detail else '-q',
                                   os.path.join(options.path, rreplace(file, args[1], args[2])),
                                   temp.name)) and options.show_time:
                    print(RESET + '%.3f second(s)' % (end-bgn))
                else:
                    sys.stdout.write(RESET)
                    sys.stdout.flush()
            else:
                print('\033[1;32m' + 'exit abnormally' + RESET)

    main()

USACO JAN10 Gold

hayturn

动态规划， \(F_m\)表示当前要做选择的奶牛在可以选择\(w_{m\ldots n-1}\)时可以获得的最大值。 \(S_m\)表示当前要做选择的奶牛做完\(w_{m\ldots n-1}\)的最优决策后，下一个奶牛可以取得的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

int w[700000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &w[i]);
    long long a = 0, b = 0;
    for (int i = n; --i >= 0; )
        if (b+w[i] >= a)
        {
            long long t = a;
            a = b+w[i];
            b = t;
        }
    printf(LLD" "LLD"\n", a, b);
}

island

根据USACL Analysis（后附），根据一个格子周围格子的布局，先把一些点转换为A，然后绕着A走一圈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
using namespace std;

const int H = 1000, W = 1000;
const int dr[] = {0,1,0,-1}, dc[] = {1,0,-1,0};
char a[H][W+1];
int tmp[4], h, w;

void DFS(int r, int c)
{
    if (a[r][c] != '.' || !r || r == h-1 || !c || c == w-1) return;
    int cntA = 0;
    for (int d = 0; d < 4; ++d)
        if (a[r+dr[d]][c+dc[d]] == 'A')
            tmp[cntA++] = d;
    switch (cntA)
    {
        case 2:
            if ((tmp[0]+tmp[1])%2 == 0 || a[r-dr[tmp[0]]-dr[tmp[1]]][c-dc[tmp[0]]-dc[tmp[1]]] != '.')
                break;
            //fall through
        case 3:
        case 4:
            a[r][c] = 'A';
            for (int d = 0; d < 4; ++d)
                DFS(r+dr[d], c+dc[d]);
    }
}

inline bool check(int r, int c)
{
    return 0 <= r && r < h && 0 <= c && c < w && a[r][c] == '.';
}

int main()
{
    scanf("%d%d", &h, &w);
    for (int r = 0; r < h; ++r)
        scanf("%s", a[r]);
    for (int r = 1; r < h-1; ++r)
        for (int c = 1; c < w-1; ++c)
            DFS(r, c);

    int r, c, rr, cc, d = 0, len = 0;
    for (r = 0; r < h; ++r)
        for (c = 0; c < w; ++c)
            if (a[r][c] == 'A')
            {
                --r;
                goto L1;
            }
L1:
    rr = r;
    cc = c;
    do
    {
        int rrr = r+dr[d+1&3], ccc = c+dc[d+1&3];
        if (check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
            d = d+1 & 3;
        }
        else if (rrr = r+dr[d], ccc = c+dc[d], check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
        }
        else if (rrr = r+dr[d+3&3], ccc = c+dc[d+3&3], check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
            d = d+3 & 3;
        }
        ++len;
    }while (r != rr || c != cc);
    printf("%d\n", len);
}

telephone

先把题目中给出的树有根化，对于一个顶点u，如果它有不超过K/2个孩子还未被分配， 可以把它们中最多2*K个在u处连接起来。如果有孤立孩子并且还未配对完K对孩子， 那么只能和u子树外的顶点配对，这相当于u是其parent的未分配顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100000;
int k, res = 0;
vector<int> e[N];

int compute(int u, int p)
{
    int t = e[u].size() == 1;
    for (vector<int>::iterator it = e[u].begin(); it != e[u].end(); ++it)
        if (*it != p)
            t += compute(*it, u);
    if (t <= k*2)
        return res += t/2, t%2;
    res += k;
    return 0;
}

int main()
{
    int n;
    scanf("%d%d", &n, &k);
    for (int i = n; --i; )
    {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    compute(0, -1);
    printf("%d\n", res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
USACO JAN10 Problem 'island' Analysis

by John Pardon

This problem requires nothing more than a modified flood-fill algorithm. Our strategy is too add squares to the main island until the optimal path is just to follow the boundary of the main island. Note that this would not work without the assumption that the main island is connected.

Consider the following four configurations:

?.?    ?..    ?.x    ?.A
A.A    A..    A..    A..
?A?    ?A?    ?A?    ?A?
(I)   (II)   (III)  (IV)
Let's focus on the center square of each of these configurations.

In (I), clearly there is no reason why FJ's ship would ever want to visit the center square; he would just have to leave again. Thus the problem remains unchanged if we change the center square to 'A'.

In (II), the situation is similar. A path like:

 V
?|.
A+->
?A?
can be changed to:

 V
?++
A.+>
?A?
with no increase in length. Thus we may change the center to square to 'A'.

In (III), we may not change the center square to an 'A', because then it wouldn't be possible to go around the main island without also going around the 'x' in the upper-right corner.

In (IV), we may also not change the center square to an 'A', at least not unless the top center square or the right center square is changed to an 'A' first.



After making the modifications (I) and (II) as many times as possible, the optimal solution is to follow the boundary of the main island, and this can just be simulated in order to find its length. Doing (I) and (II) as many times as possible is a modified flood-fill and can be done with a DFS. A solution follows:

PyGTK迷宫生成器mazer

随机生成一个迷宫 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python

from sys import stdout
from random import randrange, shuffle
import gtk

BORDER = 10
LENGTH = 24

class mazer():
    def __init__(self, maxw, maxh):
        self.maxw, self.maxh = maxw, maxh
        self.map = [[False for c in xrange(self.maxw*2+1)] for r in xrange(self.maxh*2+1)]
        self.map[randrange(1, self.maxh*2, 2)][0] = True
        self.map[randrange(1, self.maxh*2, 2)][self.maxw*2] = True
        self.DFS(randrange(1, self.maxw*2, 2), randrange(1, self.maxh*2, 2))

    def run(self):
        window = gtk.Window()
        window.set_title('mazer')
        window.connect('destroy', gtk.main_quit)

        darea = gtk.DrawingArea()
        darea.size(LENGTH*self.maxw+BORDER*2, LENGTH*self.maxh+BORDER*2)
        darea.connect('expose_event', self.expose)
        window.add(darea)

        window.show_all()
        gtk.main()

    def DFS(self, x, y):
        self.map[y][x] = True
        ds = [(1,0),(0,1),(-1,0),(0,-1)]
        shuffle(ds)
        for d in ds:
            if 0 <= x+d[0]*2 < self.maxw*2 and 0 <= y+d[1]*2 < self.maxh*2 and not self.map[y+d[1]*2][x+d[0]*2]:
                self.map[y+d[1]][x+d[0]] = True
                self.DFS(x+d[0]*2, y+d[1]*2)

    def expose(self, widget, data):
        for y in xrange(self.maxh+1):

2013年8月17日更新

现在知道这个算法的名称了：recursive backtracking，可以参见拙作完美迷宫生成算法

三柱汉诺塔相关扩展问题

设盘子编号为，编号大的尺寸大，有三根柱子。

输出初始局面（所有盘子都在1号柱子）到终止局面（所有盘子都在3号柱子）的最优方案。 时间复杂度： 经典递归，略。

输出最优方案中某一局面之前经过的步骤数。 时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int maxdisc, int src, int dst)
{
    if (pos[maxdisc] == 6-src-dst)
    {
        fprintf(stderr, "error: this is not a midway of the best solution.\n");
        exit(1);
    }
    if (pos[maxdisc] == src)
    {
        if (maxdisc > 1)
            move(maxdisc-1, src, 6-src-dst);
        pos[maxdisc] = dst;
    }
    else
    {
        nmoves += 1 << maxdisc-1;
        if (maxdisc > 1)
            move(maxdisc-1, 6-src-dst, dst);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    move(n, 1, 3);
    printf("It is a midway of the best solution and there is/are %d move(s) before.\n", nmoves);
}

输出当前局面（不一定是最优解的中间步骤）到终止局面的最优方案。 时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int disc, int dst)
{
    if (pos[disc] == dst) return;
    for (int i = disc-1; i; --i)
        move(i, 6-pos[disc]-dst);
    printf("%d: %d -> %d\n", disc, pos[disc], dst);
    pos[disc] = dst;
    ++nmoves;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);

    //for (int i = n-1; i; --i)
    //    move(i, pos[n]);

    for (int i = n; i; --i)
        move(i, 3);

    printf("total moves: %d\n", nmoves);
}

输出当前局面下，把所有盘子移动到任一根柱子的最优方案。 时间复杂度：Ο(2^N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int disc, int dst)
{
    if (pos[disc] == dst) return;
    for (int i = disc-1; i; --i)
        move(i, 6-pos[disc]-dst);
    printf("%d: %d -> %d\n", disc, pos[disc], dst);
    pos[disc] = dst;
    ++nmoves;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    for (int i = n-1; i; --i)
        move(i, pos[n]);
    printf("total moves: %d\n", nmoves);
}

输出当前局面下，把所有盘子移动到任一根柱子的最优方案所需步数。 时间复杂度：

易知，必定把移动到处 否则的话，需要至少步，不会最优。 所以所在位置就是 目标柱子

注意到如果初始时都在同一个根柱子上，那就不用再管它们了。 只需考虑

之所以要移动，要么是为了给比它编号大的盘子让路，要么是因为要把它移动到目标柱子。 所以，如果要把移动到某根柱子，那么也应该移动到柱子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

const int N = 10000;
int cnt = 0, pos[N+1];

void move(int maxdisc, int dst)
{
    if (!maxdisc) return;
    int src = pos[maxdisc], aux = 6-src-dst;
    if (src == dst)
        move(maxdisc-1, dst);
    else
    {
        move(maxdisc-1, aux);
        cnt += 1 << maxdisc-1;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    move(n-1, pos[n]);
    printf("%d\n", cnt);
}

总结一下，对于求方案的问题，因为最坏情况下步骤数可以达到，所以以上源码在渐进意义上达到最优复杂度。

对于求步骤数（无须输出方案），以上源码时间复杂度都是，由于输入时间已达到，所以在渐进意义上也达到了最优复杂度。