1519. Formula 1
Time Limit: 1.0 second
Memory Limit: 16 MB
Background
Regardless of the fact, that Vologda could not get rights to hold the Winter Olympic games of 20**, it is well-known, that the city will conduct one of the Formula 1 events. Surely, for such an important thing a new race circuit should be built as well as hotels, restaurants, international airport - everything for Formula 1 fans, who will flood the city soon. But when all the hotels and a half of the restaurants were built, it appeared, that at the site for the future circuit a lot of gophers lived in their holes. Since we like animals very much, ecologists will never allow to build the race circuit over the holes. So now the mayor is sitting sadly in his office and looking at the map of the circuit with all the holes plotted on it.
Problem
Who will be smart enough to draw a plan of the circuit and keep
the city from inevitable disgrace? Of course, only true
professionals - battle-hardened programmers from the first team of
local technical university!.. But our heroes were not looking for
easy life and set much more difficult problem: "Certainly, our
mayor will be glad, if we find how many ways of building the
circuit are there!" - they said.
It should be said, that the circuit in Vologda is going to be
rather simple. It will be a rectangle N*M cells in size with a
single circuit segment built through each cell. Each segment should
be parallel to one of rectangle's sides, so only right-angled bends
may be on the circuit. At the picture below two samples are given
for N = M = 4 (gray squares mean gopher holes, and the bold black
line means the race circuit). There are no other ways to build the
circuit here.
Input
The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located.
Output
You should output the desired number of ways. It is guaranteed, that it does not exceed 263-1.
**********************************************************************************************
题目简意:
给你一个m * n的棋盘,有的格子是障碍,问共有多少条回路使得经过每个非障碍格子恰好一次.m, n ≤ 12。
如图,m = n = 4,(1, 1), (1, 2)是障碍,共有2条满足要求的回路.
**********************************************************************************************
额……先听ccy唧唧歪歪一段吧……(时间紧张的同学们请直接跳至下一块!!!)
这是个很古老的问题,陈丹琦关于状态压缩的这篇论文也是很古老的论文,ccy其实和这篇论文接触了好几次了(仅此接触而已),陈丹琦的那个ppt,ccy看了也好多好多次了,从第一次学状态压缩,然后,后来复习状态压缩。不过,陈丹琦讲的这些东西对我来说,确实是太有难度了,以至于,我一直扑在周伟的那篇没写完的论文上。这次,吴老师说,我们要提高,于是乎,我从上个星期五开始,刻苦专研陈丹琦的这篇《基于连通性状态压缩的动态规划问题》的文。(战线拉得有点长,因为周末碰到帅哥了,额……)
话说,看那文是相当痛苦,开始还知道可以怎么去尝试实现,后来,就是感慨大牛思想,仅此,感叹,毫无办法。所以,ccy在痛苦的拉了一篇后,决定从头来,一题题的试着实现。(不过不知道能不能坚持到最后一题。)
**********************************************************************************************
我们要把p、q的插头状态转为p'和q',pq --> p'q'。
ccy代码:
#include<iostream>
using namespace std;
const int Limitn=15;
const int Limithash=1999997;
int a[Limitn][Limitn];//地图,判断线段可放不
int k,n,m,nn,mm;//k:滚动用。
int jz[Limitn];//进制移动的位数
int hash[Limithash];//hash里存的东东是当前状态在state里第几个位置
unsigned long long
state[2][600000],sum[2][600000];//state状态,sum:该状态的和
int total[2];//该格子状态的总数
int ans=0;
void init()
{
}
void prepared_jinzhi()
{
}
void Hash_in(unsigned long long s,int data)//哈希
{
}
void work()
{