ZOJ 3817 Chinese Knot （DP）

ZOJ3817 非常好的一个题。想出来了就比较简单了。题意比较清楚。大致意思就是有4条链。四条链的端点之间是可以跳过去的。然后给了一个目标字符串，要输出得到目标字符串的一个路径。因为链可以反向走，那么4条链可以变为8条链。这样其实问题转化成8条链可以跳来跳去得到目标串。如果只走一条链，那么直接hash进行判断输出。如果转移了多条链，那么只需要记录现在在哪条链的终点。然后进行转移。需要输出路径，要记录一下。

Chinese Knot

Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge

Chinese knot is a decorative handicraft that began as a form of Chinese folk artifact in the Tang and Song Dynasty in China. It was later popularized in the Ming. Alice is learning Chinese knotting. To take the first step, she went to the store and bought a string. To her surprise, she found the string was composed of characters! Anyway, she made a simple Chinese knot. It consists of one knot with 4 loops:

Look at the picture above. There are four loops connected at the center black knot. To make the image clear and neat, the characters on the string are shown as red and yellow points. As a Mid-Autumn Festival gift, Alice give this handcrafted Chinese knot to you. Then she asked you a question: You are given a target character sequence. Can you get the sequence by walking on the knot? “Walking on the knot” means:

You can start at any point you want.
You can not start at or move to the black knot in the center.
Each step, you can only move to an adjacent point, except for the point you came from immediately.
The 8 points closely around the black knot are adjacent to each other. For example, in the picture above, they are the 8 yellow points adjacent to the black knot.
Your path should not contain three continuous points which are both one of the 8 points mentioned above.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains two integers N and M (3 <= N, M <= 100000). The total length of string that Alice bought from store is 4 N. Then followed by 4 lines, each line contains N lower case letters as a loop of the Chinese knot. These characters are indexed from 1 to 4 N corresponding to the input order. The next line contains M lower case letters indicating the target character sequence.

Output

For each test case, output the M indexes of characters you visited. If there are multiple solutions, output any one. If there is no solution, output “No solution!” instead.

Sample Input

2
3 3
abc
abc
abc
abc
baa
3 3
abc
abc
abc
abc
bab

Sample Output

2 1 4
No solution!

Hint

In the first case, we start at the second character of the first loop and stop at the first character of the second loop.

Author: CHEN, Weijie Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round 代码君：

/* ***
Author :kuangbin
Created Time :2014/10/3 8:16:55
File Name :E:\2014ACM\2014网络赛\2014牡丹江\I.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
const int SEED = 133331;
int n,m;
char str[MAXN];
char ss[8][MAXN];
unsigned long long P[MAXN];
unsigned long long hs[MAXN];
unsigned long long hss[8][MAXN];
//检查ss[id]的[l1,r1] 和 str的[l2,r2]是不是一样
bool check(int id,int l1,int r1,int l2,int r2){
unsigned long long tmp1 = hss[id][r1] - hss[id][l1-1]P[(r1-l1+1)];
unsigned long long tmp2 = hs[r2] - hs[l2-1]P[(r2-l2+1)];
return tmp1 == tmp2;
}
bool first;
void output(int id,int x){
if(first)first = false;
else printf(“ “);
if(id < 4){
printf(“%d”,idn+x);
}
else printf(“%d”,(id-4)n+(n+1-x));
}
int pre[MAXN][8];
void print(int i,int id){
if(i <= n){
for(int j = n-i+1;j <= n;j++)
output(id,j);
return;
}
print(i-n,pre[i][id]);
for(int j = 1;j <= n;j++)
output(id,j);
}
void gao(){
for(int i = 0;i < 8;i++){
hss[i][0] = 0;
for(int j = 1;j <= n;j++)
hss[i][j] = hss[i][j-1]SEED + ss[i][j-1];
}
hs[0] = 0;
for(int i = 1;i <= m;i++)
hs[i] = hs[i-1]SEED + str[i-1];
first = true;
if(m <= n){
for(int i = 0;i < 8;i++)
for(int j = 1;j+m-1 <= n;j++)
if(check(i,j,j+m-1,1,m)){
for(int k = j;k <= j+m-1;k++)
output(i,k);
printf(“\n”);
return;
}
}
memset(pre,-1,sizeof(pre));
for(int i = 1;i <= m;i++)
for(int j = 0;j < 8;j++){
if(i <= n){
if(check(j,n-i+1,n,1,i))
pre[i][j] = 0;
}
//printf(“i %d j %d %d\n”,i,j,pre[i][j]);
if(pre[i][j] == -1)continue;
for(int k = 0;k < 8;k++){
if(k == j+4 || k == j-4)continue;
if(i+n >= m){
if(check(k,1,m-i,i+1,m)){
print(i,j);
for(int x = 1;x <= m-i;x++)
output(k,x);
printf(“\n”);
return;
}
continue;
}
if(check(k,1,n,i+1,i+n)){
pre[i+n][k] = j;
}
}
}
printf(“No solution!\n”);
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
P[0] = 1;
for(int i = 1;i < MAXN;i++)
P[i] = P[i-1]*SEED;
int T;
scanf(“%d”,&T);
while(T–){
scanf(“%d%d”,&n,&m);
for(int i = 0;i < 4;i++){
scanf(“%s”,ss[i]);
strcpy(ss[i+4],ss[i]);
reverse(ss[i+4],ss[i+4]+n);
}
scanf(“%s”,str);
gao();
}
return 0;
}