题目名称	913. 漫游小镇
输入输出	`betsy.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	7
题目来源	sywgz 于2012-07-12加入
开放分组	全部用户
提交状态
分类标签	USACO 动态规划搜索法插头DP
	分享题解

通过：65，提交：178，通过率：36.52%
Riolu	100	0.000 s	0.00 MiB	C++
Hakurou!	100	0.000 s	0.00 MiB	C++
9999	100	0.000 s	0.00 MiB	C++
Violet Evergarde	100	0.000 s	0.00 MiB	C++
☭寒冰烈火☭	100	0.000 s	0.00 MiB	C++
leon	100	0.000 s	0.00 MiB	C++
Tab↹	100	0.000 s	0.00 MiB	C++
Hyoi_0Koto	100	0.000 s	0.13 MiB	C++
猎户星座	100	0.000 s	0.32 MiB	C++
thomount	100	0.001 s	0.29 MiB	C++

关于漫游小镇的近10条评论(全部评论)
打表大法好，搜索直接过！！！梦那边的美好ET 2018-11-01 07:06 7楼
人生中第一道插头dp，首题留念！ FoolMike 2017-03-16 13:13 6楼
DFS+剪枝 AAAAAAAAAA 2016-07-03 11:56 5楼
咦？为啥没人打表。。清羽 2015-05-14 07:36 4楼
某篇论文上所说的剪枝优化根本过不了，最后还是得靠插头DP。。。。 mikumikumi 2015-05-03 18:51 3楼
一个妹子怎么可以这么强。。————usaco某神犇 cdq分类讨论一定学得很好。。以前一直想写。。。。一直没写。。。。几乎就是模板，和论文上几乎，不是，应该说就是一样。。。。智商有限，看论文看了半天。。。萌迪膜拜中。。。 cdq膜拜中。。。 GDFRWMY 2014-01-28 13:59 2楼
不开O2过掉，开了E一个点，累不爱使用了插头DP：逐格递推，四进制括号表示法，map判重，更新时生成状态因为没把map清空跪了一晚上 cstdio 2013-11-29 13:45 1楼

913. 漫游小镇

★★★ 输入文件：betsy.in 输出文件：betsy.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

一个正方形的镇区分为 $N^2$ 个小方块($1\leq N\leq 7$)。农场位于方格的左上角，集市位于左下角。贝茜穿过小镇，从左上角走到左下角，刚好经过每个方格一次。当 $N=3$ 时，贝茜的漫游路径可能如下图所示：

----------------
|    |    |    |
| F**********  |
|    |    | *  |
------------*---
|    |    | *  |
|  *****  | *  |
|  * | *  | *  |
---*---*----*---
|  * | *  | *  |
|  M | ******  |
|    |    |    |
----------------

写一个程序，对于给出的 $N$ 值，计算贝茜从农场走到集市有多少种唯一的路径。

【输入格式】

一个整数N($1\leq N\leq 7$)

【输出格式】

只有一行。输出一个整数表示唯一路径的数量。

【输入样例】

【输出样例】

【来源】

译 by Felicia Crazy