第一次用 Perl 做正式应用，项目地址：http://github.com/MaskRay/raybot

现在具有的功能：查询 ip 所在地，保存频道最近发言记录发送给刚近来的用户，google 翻译，用 gentoo 的 eix -e 查询软件包描述，给某个 nick 留言等

命令行选项见 ./raybot --help

比如
$ ./raybot -n xxx -p yyy -c #zzz
表示
bot 的 nick 为 xxx，密码 yyy，加入 irc.freenode.net（默认服务器）的 #zzz 频道

可以用 -a 选项设定 bot 的管理员，默认是“MaskRay”，这些是 botadmin 才能用的命令

'o nick
让 bot 给 nick 加 op 权限

'd nick
让 bot 给 nick 去除 op 权限

'j #channel
让 bot 加入 #channel

'p #channel
让 bot 离开 #channel

'q
退出

'r
重启 bot

'raw command
发送 raw 命令 command，比如 PRIVMSG MaskRay :Hello 能向 MaskRay 发送 Hello 消息

'k nick
让 bot 踢了 nick

以下是普通用户可以使用的命令

'h
查看帮助

'log
刚进频道的用户使用，让 bot 把最近的发言记录私聊给自己，或者和 bot 私聊时用 'log #channel

'nicklog nick
让 bot 把 nick 在当前频道最近的发言记录私聊给自己，或者和 bot 私聊时用 'nicklog nick #channel

'ip 8.8.8.8
查询 ip 所在地

'en2zh-tw hello, world
'zh-cn2en 你好，世界
使用 8pm 做的一个 gae 翻译文本

'whatis vim
让 bot 用 eix -e 查询软件包描述

'' expression
'' 2 / 3 + 1 * 2 + sin(1)
执行一个表达式，用 Safe 做的，安全性有保障

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

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
Device Drivers
    Network device support
        PHY Device support and infrastructure
            [M] Drivers for Broadcom PHYs
        Ethernet (100 Mbit)
            [M] Broadcom Tigon3 support
这两项都编译成模块，要保证 broadcom 在 tg3 之前加载
modprobe -r tg3
modprobe broadcom
modprobe tg3



我的 framebuffer 的配置
emerge -av v86d

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，方法是新建一个带 x 属性的文件

#!/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下，然后运行

$ update-menus

-- 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 }
                                  }
                        })

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 #include <cstdio>
  2 #include <cstring>
  3 #include <climits>
  4 #include <algorithm>
  5 using namespace std;
  6
  7 const int N = 100100;
  8 struct Card { int a, b, c, s; bool valid; } cards[N];
  9 bool cmp_by_a(const Card &x, const Card &y) {return x.a > y.a || x.a == y.a && x.s > y.s; }
 10 bool cmp_by_b(const Card &x, const Card &y) {return x.b > y.b || x.b == y.b && x.s > y.s; }
 11 bool cmp_by_c(const Card &x, const Card &y) {return x.c > y.c || x.c == y.c && x.s > y.s; }
 12
 13 const int V = 100*3+4;
 14 bool flag[V];
 15 int h[V], mincost;
 16 struct Edge {int v, c, w; Edge *next, *pair; } *e[V], pool[V*10], *pit = pool;
 17 void insert(int u, int v, int c, int w)
 18 {
 19     *pit = (Edge){v, c, w, e[u]}; e[u] = pit++;
 20     *pit = (Edge){u, 0, -w, e[v]}; e[v] = pit++;
 21     e[u]->pair = e[v];
 22     e[v]->pair = e[u];
 23 }
 24 bool relabel(int sink)
 25 {
 26     int d = INT_MAX;
 27     for (int u = 0; u <= sink; u++) if (flag[u])
 28         for (Edge *it = e[u]; it; it = it->next)
 29             if (it->c > 0 && !flag[it->v])
 30                 d = min(d, h[it->v]+it->w-h[u]);
 31     if (d == INT_MAX) return false;
 32     for (int u = 0; u <= sink; u++)
 33         if (flag[u]) h[u] += d;
 34     return true;
 35 }
 36 int augment(int u, int d, int src, int sink)
 37 {
 38     if (u == sink)
 39         return mincost += (h[src]-h[sink])*d, d;
 40     flag[u] = true;
 41     int old = d;
 42     for (Edge *it = e[u]; it; it = it->next)
 43         if (it->c > 0 && !flag[it->v] && h[it->v]+it->w == h[u]) {
 44             int dd = augment(it->v, min(d, it->c), src, sink);
 45             it->c -= dd, it->pair->c += dd;
 46             if (!(d -= dd)) break;
 47         }
 48     return old-d;
 49 }
 50
 51 int main()
 52 {
 53     int cases, n, A, B, C;
 54     for (scanf("%d", &cases); cases--; ) {
 55         scanf("%d%d%d%d", &n, &A, &B, &C);
 56         for (int i = 0; i < n; i++) {
 57             scanf("%d%d%d", &cards[i].a, &cards[i].b, &cards[i].c);
 58             cards[i].s = cards[i].a+cards[i].b+cards[i].c;
 59             cards[i].valid = false;
 60         }
 61
 62         nth_element(cards, cards+A+B+C, cards+n, cmp_by_a);
 63         for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
 64         nth_element(cards, cards+A+B+C, cards+n, cmp_by_b);
 65         for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
 66         nth_element(cards, cards+A+B+C, cards+n, cmp_by_c);
 67         for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
 68         int nn = 0;
 69         for (int i = 0; i < n; i++)
 70             if (cards[i].valid)
 71                 cards[nn++] = cards[i];
 72         n = nn;
 73
 74         const int sink = 4+n, tsrc = sink+1, tsink = tsrc+1;
 75         pit = pool;
 76         memset(e, 0, sizeof(e));
 77         mincost = 0;
 78         insert(0, 1, A, 0);
 79         insert(0, 2, B, 0);
 80         insert(0, 3, C, 0);
 81         for (int i = 0; i < n; i++) {
 82             const int foo = cards[i].s;
 83             insert(4+i, 1, 1, cards[i].a*100000+foo); mincost -= cards[i].a*100000+foo;
 84             insert(4+i, 2, 1, cards[i].b*100000+foo); mincost -= cards[i].b*100000+foo;
 85             insert(4+i, 3, 1, cards[i].c*100000+foo); mincost -= cards[i].c*100000+foo;
 86             insert(tsrc, 4+i, 3, 0);
 87             insert(4+i, sink, 1, 0);
 88         }
 89         insert(1, tsink, n, 0);
 90         insert(2, tsink, n, 0);
 91         insert(3, tsink, n, 0);
 92         insert(sink, 0, INT_MAX, 0);
 93
 94         memset(h, 0, sizeof(h));
 95         do while (memset(flag, 0, sizeof(flag)), augment(tsrc, INT_MAX, tsrc, tsink));
 96         while (relabel(tsink));
 97         do while (memset(flag, 0, sizeof(flag)), augment(0, INT_MAX, 0, sink));
 98         while (relabel(sink));
 99         printf("%d %d\n", (-mincost)/100000, (-mincost)%100000);
100     }
101 }

题目大意：有一个长为 N 的整数数列，每次可以把一个数增减一，求最少次数使得有连续 K 个数相同。
下面程序用 Size balanced tree 实现，卫星数据是子树节点数和子树关键字和。

  1 #include <cstdio>
  2 #include <climits>
  3 #include <algorithm>
  4 using namespace std;
  5
  6 const int N = 100000;
  7 int a[N];
  8
  9 struct Node *null, *pit, *root;
 10 struct Node
 11 {
 12     int key, size;
 13     long long sum;
 14     Node *ch[2];
 15     Node() {}
 16     Node(int key) : key(key), size(1), sum(key) {ch[0] = ch[1] = null; }
 17     void update() {
 18         size = ch[0]->size + 1 + ch[1]->size;
 19         sum = ch[0]->sum + key + ch[1]->sum;
 20     }
 21 }pool[N+1];
 22
 23 void zag(Node *&x, int d)
 24 {
 25     Node *y = x->ch[!d];
 26     x->ch[!d] = y->ch[d];
 27     y->ch[d] = x;
 28     y->size = x->size;
 29     y->sum = x->sum;
 30     x->update();
 31     x = y;
 32 }
 33
 34 void maintain(Node *&x, int d)
 35 {
 36     if (x == null) return;
 37     if (x->ch[d]->ch[d]->size > x->ch[!d]->size)
 38         zag(x, !d);
 39     else if (x->ch[d]->ch[!d]->size > x->ch[!d]->size)
 40         zag(x->ch[d], d), zag(x, !d);
 41     else return;
 42     maintain(x->ch[0], 0);
 43     maintain(x->ch[1], 1);
 44     maintain(x, 0);
 45     maintain(x, 1);
 46 }
 47
 48 void insert(Node *&x, int key)
 49 {
 50     if (x == null) {
 51         x = new Node(key);
 52         return;
 53     }
 54     int d = x->key < key;
 55     ++x->size;
 56     x->sum += key;
 57     insert(x->ch[d], key);
 58     maintain(x, d);
 59 }
 60
 61 Node *erase(Node *&x, int key)
 62 {
 63     if (x->key == key || key < x->key && x->ch[0] == null || key > x->key && x->ch[1] == null) {
 64         if (x->ch[0] == null || x->ch[1] == null) {
 65             Node *y = x;
 66             x = x->ch[x->ch[0] == null];
 67             return y;
 68         }
 69         Node *y = erase(x->ch[1], key-1);
 70         x->key = y->key;
 71         x->update();
 72         return null;
 73     }
 74     Node *y = erase(x->ch[x->key < key], key);
 75     x->update();
 76     return y;
 77 }
 78
 79 long long tot, mid;
 80 void count(Node *&x, int cnt)
 81 {
 82     if (x->ch[0]->size == cnt) {
 83         mid = x->key;
 84         tot += x->ch[0]->sum + x->key;
 85     } else if (x->ch[0]->size > cnt)
 86         count(x->ch[0], cnt);
 87     else
 88         tot += x->ch[0]->sum + x->key,
 89         count(x->ch[1], cnt-x->ch[0]->size-1);
 90 }
 91
 92 int main()
 93 {
 94     pit = pool;
 95     root = null = new Node(0); null->size = 0; null->ch[0] = null->ch[1] = null;
 96
 97     int n, k;
 98     scanf("%d%d", &n, &k);
 99     for (int i = 0; i < n; i++)
100         scanf("%d", &a[i]);
101
102     long long best = LLONG_MAX;
103     int res1, res2, res3;
104     for (int i = 0; i < k-1; i++)
105         insert(root, a[i]);
106     for (int i = k-1; i < n; i++) {
107         insert(root, a[i]);
108         tot = 0;
109         count(root, k/2);
110         long long t = mid*(k/2+1)-tot + root->sum-tot-mid*(k-k/2-1);
111         if (t < best) {
112             best = t;
113             res1 = i-k+1;
114             res2 = i;
115             res3 = mid;
116         }
117         erase(root, a[i-k+1]);
118     }
119
120     printf("%lld\n", best);
121     for (int i = res1; i <= res2; i++)
122         a[i] = res3;
123     for (int i = 0; i < n; i++)
124         printf("%d\n", a[i]);
125 }

Vim
采用 ir_black 配色方案
使用 syntax/2html.vim 生成 codes 的 html 版本
然后复制到这里
为了配合 ir_black ，blog 只好采用黑底
可惜 is-programmer 找不到满意的黑底主题

 1 #!/usr/bin/env python
 2 #
 3 #   Copyright (C) 2010 MasterRay (masterraysoul at gmail dot com)
 4 #                               http://code.google.com/p/rayup/
 5 #
 6 #   This program is free software: you can redistribute it and/or modify
 7 #   it under the terms of the GNU General Public License as published by
 8 #   the Free Software Foundation, either version 3 of the License, or
 9 #   (at your option) any later version.
10 #  
11 #   This program is distributed in the hope that it will be useful,
12 #   but WITHOUT ANY WARRANTY; without even the implied warranty of
13 #   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 #   GNU General Public License for more details.
15 #  
16 #   You should have received a copy of the GNU General Public License
17 #   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 #
19 #   ------------------------------------------------------------------------------
20 #
21 #   checker
22 #           check programs using testdata
23
24 COPYING = '''checker
25 Copyright (C) 2010 MasterRay
26 This is free software; see the source for copying conditions. There is NO
27 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
28 '''
29
30 def rreplace(s1, s2, s3):
31     p = s1.rfind(s2)
32     return s1[:p] + s3 + s1[p+len(s2):] if p != -1 else s1
33
34 def test(s, pat1, pat2):
35     p = s.find(pat1)
36     if p == -1:
37         return False
38     q = s.find(pat2)
39     while q != -1:
40         if not p <= q < p+len(pat1):
41             return True
42         q = s.find(pat2, q+len(pat2))
43     return False
44
45 if __name__ == '__main__':
46
47     import sys, os, re
48     from optparse import OptionParser
49
50     def main():
51
52         def print_copying():
53             sys.stdout.write(COPYING)
54             exit(0)
55
56         usage = '''usage: %prog source [input] [output]
57         source  - source file
58         input   - suffix of input files (default 'in')
59         output  - suffix of output files (default 'out')'''
60         parser = OptionParser(usage=usage)
61         parser.add_option('-p', '--path', action='store',
62                 dest='path', default='/tmp',
63                 help='specify the path of testdata')
64         parser.add_option('-i', '--dataid', action='store',
65                 dest='dataid', default='', help='specify the data id')
66         parser.add_option('-d', '--detail', action='store_true',
67                 dest='show_detail', default=False, help='show details')
68         parser.add_option('-t', '--time', action='store_true',
69                 dest='show_time', default=False, help='show time used')
70         parser.add_option('--version', action="callback",
71                 callback=lambda o, s, v, p: print_copying(),
72                 help="print the COPYING and exit")
73         (options, args) = parser.parse_args()
74
75         options.path = os.path.expanduser(options.path)
76         if len(args) < 1 or len(args) > 4:
77             parser.print_usage()
78             sys.exit(1)
79         if len(args) < 2:
80             args.append('in')
81         if len(args) < 3:
82             args.append('out')
83         r = re.compile('\d+')
84         for file in sorted([file for file in os.listdir(options.path) if test(file,
85             args[0], args[1])], key = lambda x : int(r.findall(x)[-1])):
86             if options.dataid != '' and r.findall(file)[-1] != options.dataid:
87                 continue
88             print('---' + file + '---')
89             os.system('%s ./main < /tmp/%s > temp' %
90                     ('time -p' if options.show_time else '', file))
91             os.system('diff -b %s /tmp/%s temp' % ('' if options.show_detail
92                     else '-q', rreplace(file, args[1], args[2])))
93
94     main()

hayturn

动态规划， 表示当前要做选择的奶牛在可以选择时可以获得的最大值。表示当前要做选择的奶牛做完的最优决策后，下一个奶牛可以取得的最大值。

[tex]If \;\; W_m+S_{m+1} >= F_{m+1}, \;\; then \;\; F_m=W_m+S_{m+1}, \;\; S_m=F_{m+1}[/tex]

[tex]If \;\; W_m+S_{m+1} >= F_{m+1}, \;\; then \;\; F_m=F_{m+1}, \;\; S_m=S_{m+1}[/tex]

#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 走一圈。

#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 的未分配顶点。

#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);
}

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: