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

动态规划, $Fm$表示当前要做选择的奶牛在可以选择$w{m\ldots n-1}$时可以获得的最大值。
$Sm$表示当前要做选择的奶牛做完$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\sim N$,编号大的尺寸大,有三根柱子$1\sim 3$。

输出初始局面(所有盘子都在1号柱子)到终止局面(所有盘子都在3号柱子)的最优方案。
时间复杂度:$O(2^N)$
经典递归,略。

输出最优方案中某一局面之前经过的步骤数。
时间复杂度:$O(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
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);
}

输出当前局面(不一定是最优解的中间步骤)到终止局面的最优方案。
时间复杂度:$Ο(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
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);
}

输出当前局面下,把所有盘子移动到任一根柱子的最优方案所需步数。
时间复杂度:$Ο(N)$

易知,必定把$1\sim N-1$移动到$N$处
否则的话,需要至少$2^{N-1}$步,不会最优。
所以$N$所在位置就是 目标柱子

注意到如果$N,N-1,\ldots,k+1$初始时都在同一个根柱子上,那就不用再管它们了。
只需考虑$k,\ldots,1$

之所以要移动$i$,要么是为了给比它编号大的盘子让路,要么是因为要把它移动到目标柱子。
所以,如果要把$i$移动到某根柱子$X$,那么$i-1,i-2,\ldots,1$也应该移动到柱子$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
#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);
}

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

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

GTK+黑白棋reversi

language: C99 + GTK+
algorithm:对棋盘各个格子设置权值,计算总值
icon:程序截图
license: GNU General Public License v3
revision control: Mercurial
bead-black.png bead-white.png texture1.png texture2.png: 8pm(http://hi.baidu.com/eightpm) 提供

gdk透明贴图好像有点麻烦(以前 Win32 API 用得是 TransparentBlt)

菜单采用GtkUIManager,可以看demo:/usr/share/gtk-2.0/demo/ui_manager.c的透明贴图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void pixbuf_transparent(GdkPixbuf *dst, const GdkPixbuf *src, gint dstx, gint dsty, guint transcolor)
{
guchar r = (transcolor & 0xFF0000) >> 16;
guchar g = (transcolor & 0x00FF00) >> 8;
guchar b = transcolor & 0x0000FF;
guchar *p = gdk_pixbuf_get_pixels(dst),
*q = gdk_pixbuf_get_pixels(src);
int d = gdk_pixbuf_get_n_channels(src),
dd = gdk_pixbuf_get_rowstride(src),
d2 = gdk_pixbuf_get_n_channels(dst),
dd2 = gdk_pixbuf_get_rowstride(dst),
w = gdk_pixbuf_get_width(src),
h = gdk_pixbuf_get_height(src);
for (int y = 0; y < h; ++y)
for (int x = 0; x < w; ++x)
{
guchar *pp = p + (dsty+y) * dd2 + (dstx+x) * d2;
guchar *qq = q + y * dd + x * d;
if (qq[0] != r || qq[1] != g || qq[2] != b)
pp[0] = qq[0], pp[1] = qq[1], pp[2] = qq[2];
}
}

GTK+ tic-tac-toe(井字棋)

语言:C99
图标是随手涂鸦的
界面部分抄袭 http://sourceforge.net/projects/tictactoegtk/(作者:Obada Denis(obadadenis@gmail.com),javajox(javajox@users.sourceforge.net))
算法是 min-max search
版本控制系统采用 8pm 推荐的 Mercurial
项目首页:http://code.google.com/p/rayup/ #里面还有些其他乱七八糟的东西
Download:hg clone https://rayup.googlecode.com/hg/ rayup
没有安装 Mercurial 的话,可以访问 http://code.google.com/p/rayup/source/browse/,手动下载一个个文件……

称球问题扩展——根据当前已知信息选择最优称量方案

似乎是某个TopCoder SRM的题目。

N 个球,有一个是坏的,坏球重量与好球不同(略轻/重于好球)。有一个天平,可以告知左右两边孰重孰轻,最小化最坏情况下称量次数,给出称量方案。下面讨论该问题的一个扩展——如何通过已知信息(即之前称量结果,之前的称量结果可能不是最优的)选择下一步称量方案,最小化最坏情况下的称量次数。

根据已有信息把所有球分为4类:

  • 肯定是好球
  • 不可能比好球轻(不能确定是否为坏球)
  • 不可能比好球重(不能确定是否为坏球)
  • 不知道任何信息

每个球必定属于以上四类中的某一类。我们只需知道每一类的数目即可,具体编号无关紧要。令$s[nh][nl][nu]$表示有$nh$个1类球,nl 个2类球,nu 个3类球,最坏情况下需要称量的次数。枚举一边放置的各类型球数 lh(1类),ll(2类),lu(3类),枚举另一边放置的各类型球数 rh(1类),rl(2类),ru(3类),re(0类)。如果两边都有0类球,那么我们可以在两边各移去一个。我们可以保证0类球只出现在一边,不妨设为 rh(1类),rl(2类),ru(3类) 一边。

Read More

NOIP 2004 数字游戏(虫食算)

下面程序可计算如下形式的式子:

1
2
3
4
5
6
7
8
9
10
11
one
+ nine
+ fifty
+twenty
-------
eighty
a
+a
--
bc

方法是枚举进位+解方程,涉及的字母以及各个位上的进位作为变量,然后解方程。这样可以用 各个位上的进位 和 字母变量中的自由变量 表示 其他字母变量。枚举 各个位上的进位 和 字母变量中的自由变量 以求出 其他字母变量,以此得到各组解。使用方法:根据要求解的式子设置各个变量,N、M设置得大点没关系,L要正好等于式子的行数,然后输入L行字符串

Read More

Dancing Links+Algorithm 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
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
#include <algorithm>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 9, LEN = 3; //size
const int MAX_R = N*N*N, MAX_C = N*N*4, MAX = MAX_C+1+MAX_R*4;
int L[MAX], R[MAX], U[MAX], D[MAX], size[MAX_C+1], column[MAX];
int res[N*N]; //result
pair<int, int> mean[MAX]; //first: pos. second: number
int mapping[256];
char mapping2[N];
void insert(int cur, int left, int right, int top)
{
L[cur] = left; R[cur] = right;
U[cur] = U[top]; D[U[cur]] = cur;
D[cur] = top; U[top] = cur;
column[cur] = top;
++size[top];
}
void remove(int c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for (int i = D[c]; i != c; i = D[i])
for (int j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--size[column[j]];
}
}
void resume(int c)
{
for (int i = U[c]; i != c; i = U[i])
for (int j = L[i]; j != i; j = L[j])
{
U[D[j]] = j;
D[U[j]] = j;
++size[column[j]];
}
L[R[c]] = c;
R[L[c]] = c;
}
bool DLX(int k)
{
if (R[MAX_C] == MAX_C) return true;
int c, mins = numeric_limits<int>::max();
for (int i = R[MAX_C]; i != MAX_C; i = R[i])
if (size[i] < mins)
mins = size[i], c = i;
remove( c );
for (int i = D[c]; i != c; i = D[i])
{
for (int j = R[i]; j != i; j = R[j])
remove(column[j]);
res[mean[i].first] = mean[i].second;
if (DLX(k+1)) return true;
for (int j = L[i]; j != i; j = L[j])
resume(column[j]);
}
resume( c );
return false;
}
int main()
{
char str[N*N+1], tmp[N*N+1];
str[0] = 0;
mapping['1'] = 0; mapping2[0] = '1';
mapping['2'] = 1; mapping2[1] = '2';
mapping['3'] = 2; mapping2[2] = '3';
mapping['4'] = 3; mapping2[3] = '4';
mapping['5'] = 4; mapping2[4] = '5';
mapping['6'] = 5; mapping2[5] = '6';
mapping['7'] = 6; mapping2[6] = '7';
mapping['8'] = 7; mapping2[7] = '8';
mapping['9'] = 8; mapping2[8] = '9';
while (strlen(str) < N*N)
scanf("%s", tmp), strcat(str, tmp);
int cur = MAX_C+1;
for (int i = 0; i <= MAX_C; ++i)
{
L[i] = i-1; R[i] = i+1;
U[i] = i; D[i] = i;
size[i] = 0;
}
L[0] = MAX_C; R[MAX_C] = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (str[i*N+j] == '.')
{
for (int k = 0; k < N; ++k)
{
insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
}
}
else
{
const int k = mapping[str[i*N+j]];
insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
res[i*N+j] = k;
}
if (!DLX(0))
puts("No solution.");
else
for (int i = 0; i < N; ++i, puts(""))
for (int j = 0; j < N; ++j)
putchar(mapping2[res[i*N+j]]);
}

2013年8月17日更新

NOIP 2009考了靶形数独,可能前一天我还敲了一遍这段代码……