首页 > 搜索 > DFS搜索 > HDU 4246-A Famous Airport Manager-DFS-[解题报告]HOJ
2015
05-23

HDU 4246-A Famous Airport Manager-DFS-[解题报告]HOJ

A Famous Airport Manager

问题描述 :

Mr. B is an airport manager. One day after lunch he looked out of his office and found that the color of each plane in the airport is either blue or green. Before supper he looked the airport again, and found that no plane is in the airport now. He couldn’t remember the order in which the planes took off, but he knew between his two observations no plane had arrived at the airport. In addition, while one plane is setting its way to the takeoff area, the remaining planes must stay at their own position and not move. In other words, considering the planes taking off in a specific order, the first plane will move while others stay at their own position. After the first plane took off, the second plane could move to the takeoff area and so on, until all the planes gone. Now he wants you to find out the number of different possible color sequences he might see, if he watched at the takeoff area during the whole afternoon.

The airport can be divided into 9 square areas (3 rows x 3 columns), and at most one plane can be parked in one area. The area located at the first column of the first row is the "takeoff area". The plane can take off only in the takeoff area. Besides, each plane (including the one in the takeoff area) can move to a vacant neighboring area. Two areas are neighboring if and only if they share an edge.

输入:

Each test case contains 3 lines, each of which contains 3 characters ‘*’, ‘B’, ‘G’, denoting that the corresponding area is currently vacant, occupied by a blue plane, or occupied by a green plane, respectively. The first character of the first row is always a ‘*’. There is at least one place in the apron.

There are about 30,000 test cases. Be careful!

输出:

Each test case contains 3 lines, each of which contains 3 characters ‘*’, ‘B’, ‘G’, denoting that the corresponding area is currently vacant, occupied by a blue plane, or occupied by a green plane, respectively. The first character of the first row is always a ‘*’. There is at least one place in the apron.

There are about 30,000 test cases. Be careful!

样例输入:

*BB
BBB
BBB
*GB
BBB
BBB

样例输出:

Case 1: 1
Case 2: 8


做了1天,实在做不出来,老TLE,只能打表了,说多了都是泪

/************************************************\
LINK: http://acm.hdu.edu.cn/showproblem.php?pid=4246
CATEGORY: Fudan Local Programming Contest 2012
AUTHOR: [email protected]
TAG:
LEVEL: B+
MEMO: v3使用打表
\************************************************/
#include<stdio.h>
#include<string.h>
#define NN 9
#define L 6561
int ans[L]={1,1,1,1,1,2,1,2,1,1,1,2,1,1,3,2,3,3,1,2,1,2,3,3,1,3,1,1,1,2,1,1,2,2,3,3,1,1,3,1,1,3,3,4,6,2,3,3,3,4,5,3,6,4,1,2,1,2,3,3,1,2,1,2,3,3,3,4,6,3,5,4,1,3,1,3,6,4,1,3,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,3,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,8,10,3,6,4,6,10,10,4,9,5,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,3,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,8,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,2,3,5,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,3,4,6,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,5,9,9,4,9,5,1,1,3,1,1,4,3,3,6,1,1,4,1,1,5,4,4,10,3,3,6,3,4,9,6,6,10,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,9,6,10,10,3,4,6,4,5,10,6,8,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,15,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,8,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,14,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,13,5,14,6,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,2,5,3,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,5,9,9,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,3,6,4,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,8,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,13,15,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,14,14,4,10,5,10,20,15,5,14,6,1,3,1,3,6,3,1,4,1,3,6,3,6,10,6,3,9,4,1,4,1,4,10,4,1,5,1,3,6,4,6,10,8,4,10,5,6,10,9,10,15,15,9,19,14,4,10,5,10,20,13,5,15,6,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,5,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,4,4,5,10,4,5,10,5,6,13,10,15,20,3,3,6,3,4,6,6,8,10,3,4,6,4,5,10,6,9,10,6,9,10,9,14,16,10,17,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,18,15,4,9,5,9,16,14,5,13,6,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,3,4,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,4,5,10,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,9,14,19,10,19,15,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,9,14,19,10,19,15,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,9,14,18,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,14,20,27,20,35,35,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,20,33,35,10,19,15,18,30,33,15,33,21,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,9,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,9,14,19,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,16,14,4,10,5,10,20,15,5,14,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,13,15,6,10,10,10,15,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,14,6,7,18,13,19,29,10,15,20,15,21,32,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,25,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,16,9,19,14,4,10,5,10,20,14,5,15,6,6,10,10,10,15,17,10,20,15,10,15,19,15,21,29,19,34,34,10,20,15,20,35,32,15,35,21,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,28,20,5,14,6,14,30,20,6,19,7,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,13,9,14,16,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,13,6,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,3,6,3,6,10,8,3,6,4,6,10,9,10,15,17,9,16,14,3,6,4,6,10,9,4,10,5,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,16,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,9,19,14,5,14,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,9,10,9,14,19,10,16,15,4,5,9,5,6,13,9,14,16,5,6,14,6,7,19,14,20,30,9,14,16,14,20,28,16,30,25,6,10,10,10,15,20,10,17,15,10,15,20,15,21,35,20,32,35,10,19,15,19,34,34,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,13,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,25,14,30,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,32,21,5,14,6,13,29,19,6,18,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,3,9,4,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,4,10,5,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,9,18,14,4,10,5,10,20,15,5,15,6,6,10,10,10,15,18,10,20,15,10,15,19,15,21,33,18,33,30,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,14,27,20,5,15,6,15,35,21,6,19,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,4,4,5,10,4,5,10,5,6,13,10,15,20,3,3,6,3,4,6,6,8,10,3,4,6,4,5,10,6,9,10,6,9,10,9,14,16,10,17,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,18,15,4,9,5,9,16,14,5,13,6,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,4,10,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,13,10,15,20,3,4,6,4,5,10,6,8,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,18,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,9,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,8,6,10,10,4,5,10,5,6,13,9,14,19,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,8,5,6,10,10,10,15,20,9,15,14,4,10,5,10,20,15,5,13,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,12,15,6,10,10,10,15,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,13,6,7,18,12,18,25,10,15,20,15,21,32,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,23,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,16,9,19,14,4,10,5,10,20,13,5,15,6,6,10,10,10,15,17,10,20,15,10,15,19,15,21,28,19,34,34,10,20,15,20,35,30,15,35,21,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,27,20,5,13,6,13,26,19,6,18,7,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,10,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,10,15,20,10,19,15,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,14,10,15,20,1,1,5,1,1,5,5,6,15,1,1,5,1,1,5,5,6,15,5,6,15,6,7,19,15,21,35,4,4,10,4,5,10,10,13,20,4,5,10,5,6,15,10,14,20,10,14,20,14,20,30,20,32,35,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,15,21,31,20,35,35,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,31,34,15,32,21,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,10,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,10,15,20,10,19,15,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,14,10,15,20,1,1,5,1,1,5,5,6,15,1,1,5,1,1,5,5,6,15,5,6,15,6,7,19,15,21,35,4,4,10,4,5,10,10,13,20,4,5,10,5,6,15,10,14,20,10,14,20,14,20,30,20,32,35,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,15,21,31,20,35,35,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,31,34,15,33,21,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,9,14,19,6,10,10,10,15,20,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,14,20,34,10,15,20,15,21,33,20,35,35,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,19,30,34,10,20,15,20,35,35,15,33,21,4,5,10,5,6,13,10,15,20,5,6,13,6,7,19,12,18,25,10,15,20,15,21,33,20,35,35,5,6,15,6,7,18,15,21,35,6,7,19,7,8,23,18,25,44,15,21,35,21,28,51,35,56,70,10,13,20,13,19,26,20,30,35,13,19,26,19,26,45,25,39,44,20,33,35,33,54,61,35,63,56,6,10,10,10,15,19,10,20,15,10,15,19,15,21,31,19,34,34,10,20,15,20,35,33,15,35,21,10,15,20,15,21,31,20,35,35,15,21,34,21,28,48,34,55,69,20,35,35,35,56,63,35,70,56,10,19,15,19,31,34,15,32,21,19,31,34,31,46,65,34,61,55,15,33,21,33,61,54,21,51,28,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,2,3,5,3,4,6,5,9,9,3,4,9,4,5,10,9,14,19,5,9,9,9,14,16,9,19,14,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,14,6,3,3,6,3,4,6,6,9,10,3,4,6,4,5,10,6,10,10,6,9,10,9,14,16,10,19,15,3,4,9,4,5,9,9,14,19,4,5,9,5,6,14,9,14,19,9,14,19,14,20,28,19,34,34,6,6,10,6,10,10,10,15,15,6,10,10,10,15,20,10,19,15,10,16,15,16,30,25,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,5,9,8,9,14,14,8,15,13,9,14,18,14,20,27,18,30,33,8,15,13,15,24,25,13,29,19,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,33,21,5,14,6,14,30,20,6,18,7,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,16,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,14,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,9,10,9,14,19,10,19,15,4,5,9,5,6,13,9,14,19,5,6,14,6,7,19,14,20,30,9,14,19,14,20,28,19,34,34,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,20,32,35,10,19,15,19,34,34,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,25,14,30,20,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,33,21,5,14,6,14,30,20,6,18,7,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,9,19,14,4,10,5,10,20,15,5,15,6,5,9,9,9,14,15,9,19,14,9,14,19,14,20,29,18,33,33,9,19,14,19,34,30,14,34,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,14,29,20,5,15,6,15,35,21,6,19,7,6,9,10,9,14,16,10,19,15,9,14,16,14,20,30,15,28,24,10,19,15,19,34,31,15,34,21,9,14,19,14,20,27,19,34,34,14,20,28,20,27,47,27,47,49,19,34,34,34,55,61,34,69,55,10,16,15,16,30,25,15,28,21,16,30,25,30,50,55,24,46,35,15,31,21,31,65,46,21,48,28,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,28,20,5,13,6,13,26,19,6,19,7,8,15,12,15,24,23,12,25,18,15,24,28,24,35,46,27,49,47,12,25,18,25,44,39,18,44,25,5,14,6,14,30,20,6,18,7,14,30,20,30,55,50,20,47,27,6,19,7,19,45,26,7,23,8,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,13,9,14,16,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,13,6,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,3,6,3,6,10,8,3,6,4,6,10,9,10,15,17,9,16,14,3,6,4,6,10,9,4,10,5,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,9,4,10,5,3,4,6,4,5,8,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,9,14,15,10,20,15,3,6,4,6,10,10,4,8,5,6,10,10,10,15,20,10,18,15,4,10,5,9,19,14,5,13,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,16,15,4,5,9,5,6,13,9,14,16,5,6,13,6,7,18,13,19,26,9,14,16,14,20,27,16,30,25,6,10,10,10,15,20,10,17,15,10,15,20,15,21,35,20,30,35,10,19,15,19,34,34,15,28,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,12,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,23,14,30,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,32,21,5,13,6,12,25,18,6,18,7,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,14,6,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,4,1,5,1,3,6,4,6,10,8,4,10,5,6,10,9,10,15,18,9,19,14,4,10,5,10,20,13,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,5,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,19,10,20,15,2,5,3,5,9,9,3,6,4,5,9,9,9,14,19,9,16,14,3,9,4,9,19,14,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,14,6,7,18,14,20,30,10,15,20,15,21,33,20,35,35,5,8,9,8,13,15,9,14,14,8,13,15,13,19,29,15,25,24,9,18,14,18,33,30,14,27,20,3,6,3,6,10,9,3,6,4,6,10,9,10,15,19,9,16,14,3,6,4,6,10,10,4,10,5,6,10,6,10,15,15,6,10,10,10,15,16,15,21,29,16,25,30,6,10,10,10,15,19,10,20,15,3,9,4,9,19,14,4,9,5,9,19,14,19,34,34,14,28,20,4,9,5,9,19,14,5,14,6,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,9,14,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,14,20,29,20,35,35,5,9,9,9,14,19,9,15,14,9,14,19,14,20,34,19,30,34,9,19,14,18,33,33,14,29,20,4,5,9,5,6,13,9,14,16,5,6,13,6,7,19,13,19,26,9,14,16,14,20,28,16,30,25,5,6,14,6,7,18,14,20,30,6,7,19,7,8,23,19,26,45,14,20,30,20,27,47,30,50,55,8,12,15,12,18,25,15,23,24,12,18,25,18,25,44,25,39,44,15,28,24,27,47,49,24,46,35,6,10,9,10,15,19,9,16,14,10,15,19,15,21,34,19,31,34,9,16,14,15,24,28,14,30,20,10,15,16,15,21,28,16,25,30,15,21,31,21,28,48,31,46,65,16,25,30,24,35,46,30,55,50,9,19,14,19,34,34,14,27,20,19,34,34,34,55,69,34,61,55,14,28,20,27,49,47,20,47,27,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,16,14,4,10,5,10,20,15,5,14,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,14,6,7,18,14,20,30,10,15,20,15,21,33,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,25,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,6,10,10,10,15,18,10,20,15,10,15,19,15,21,29,19,34,34,10,20,15,20,35,32,15,35,21,4,9,5,9,19,14,5,13,6,9,19,14,19,34,34,14,28,20,5,14,6,14,30,20,6,19,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,10,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,10,20,15,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,15,6,6,10,10,10,15,19,10,20,15,10,15,19,15,21,32,19,34,31,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,31,21,5,15,6,15,35,21,6,19,7,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,4,1,4,10,5,1,5,1,4,10,4,10,20,13,4,10,5,10,20,14,20,35,32,14,30,20,4,10,5,10,20,14,5,15,6,1,5,1,5,15,6,1,5,1,5,15,6,15,35,21,6,19,7,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,20,15,4,10,5,9,19,14,5,15,6,6,10,10,10,15,18,10,20,15,10,15,20,15,21,33,20,35,35,10,20,15,19,34,30,15,35,21,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,33,21,5,15,6,14,34,20,6,19,7,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,34,34,15,31,21,10,15,19,15,21,32,19,34,31,15,21,33,21,28,51,33,54,61,19,34,31,34,55,61,31,65,46,10,20,15,20,35,35,15,31,21,20,35,35,35,56,70,35,63,56,15,34,21,34,69,55,21,48,28,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,33,21,5,13,6,12,25,18,6,19,7,10,20,13,20,35,30,13,26,19,20,35,33,35,56,63,33,61,54,13,26,19,25,44,39,19,45,26,5,15,6,15,35,21,6,18,7,15,35,21,35,70,56,21,51,28,6,19,7,18,44,25,7,23,8,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,10,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,10,20,15,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,15,6,6,10,10,10,15,19,10,20,15,10,15,19,15,21,33,19,34,31,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,31,21,5,15,6,15,35,21,6,19,7,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,4,1,4,10,5,1,5,1,4,10,4,10,20,13,4,10,5,10,20,14,20,35,32,14,30,20,4,10,5,10,20,14,5,15,6,1,5,1,5,15,6,1,5,1,5,15,6,15,35,21,6,19,7,1,5,1,5,15,6,1,5,1};
int main(){
char str[10];char ch;int k,layout;int ic=1;
while (~scanf("%3s",str)){
scanf("%3s%3s",str+3,str+6);
layout=0;
for (k=1;k<NN;k++){
layout*=3;
if (str[k]=='B') layout+=1;
if (str[k]=='G') layout+=2;
}
printf("Case %d: %d\n",ic++,ans[layout]);

}
return 0;
}


生成数据的代码

/************************************************\
LINK: http://acm.hdu.edu.cn/showproblem.php?pid=4246
CATEGORY: Fudan Local Programming Contest 2012
AUTHOR: [email protected]
TAG:
LEVEL: B+
\************************************************/
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#define N 3
#define NN N*N
#define M 2000
#define L 6561
using namespace std;
struct ST{
bool can[N][N]; //当前点是否可候选(即能否直达0点)
};
bool chk[N][N]; //当前点是否已遍历
int seq[NN];int nseq; //temp sequence for DFS
int vldseqs[M][NN];int nvldseqs; //valid sequences calculated by DFS
int dirs[][2]={{0,1},{1,0},{0,-1},{-1,0}};
int ans[L];
void dfs(ST st,int i,int j){
if (i<0||i>=N||j<0||j>=N||chk[i][j]) return;
if (nseq==NN-1){ //save the possible seq
seq[NN-1]=i*N+j;
for (int k=0;k<NN;k++) vldseqs[nvldseqs][k]=seq[k];
nvldseqs++;
return;
}
chk[i][j]=1; //update chk
int tmp=nseq;
seq[nseq++]=i*N+j;
int k,ii,jj;
for (k=0;k<4;k++){ //update st
ii=i+dirs[k][0];
jj=j+dirs[k][1];
if (ii>=0&&ii<N&&jj>=0&&jj<N) st.can[ii][jj]=1;
}
for (ii=0;ii<N;ii++)
for (jj=0;jj<N;jj++)
if (st.can[ii][jj]) dfs(st,ii,jj);
chk[i][j]=0;
nseq=tmp;
}

int main(){

int i,j,k;ST st;
memset(chk,0,sizeof(chk));
memset(st.can,0,sizeof(st.can));
st.can[0][0]=1;
dfs(st,0,0);
//for (i=0;i<nvldseqs;i++) {for (j=0;j<NN;j++) printf("%d ",vldseqs[i][j]);printf("\n");};//test
int layout[NN];int x,lay,iseq,kind;
layout[0]=0;
map<int,bool> kmap;
for (lay=0;lay<L;lay++){
k=NN-1;x=lay;
while (k>0){
layout[k--]=x%3;
x=x/3;
}
kmap.clear();
for (iseq=0;iseq<nvldseqs;iseq++){
kind=0;
for (int k=0;k<NN;k++){
x=layout[vldseqs[iseq][k]];
if (x==1) kind=(kind<<1)+0;
if (x==2) kind=(kind<<1)+1;
}
kmap[kind]=1;
}
ans[lay]=kmap.size();

}
freopen("hdu4246.sub.o","w",stdout);
for (i=0;i<L;i++) printf("%d,",ans[i]);
return 0;
}

参考:http://huangzkhuang.blog.163.com/blog/static/79451749201422391615451/


,