2014
03-06

Pipes

After writing a solver for the "moveable maze" game last week, you have grown tired of it. After all, you already know the optimal solution. To entertain yourself, you find another puzzle game called "Pipes", and play that for a while. On one puzzle, you have not been able to find a solution by hand, and you think that there is no solution. You decide to write a program to tell you whether this is the case.

The game is played on a grid with R rows and C columns. Each square of the grid contains a black dot in the centre and black lines in the direction of some, none, or all of its north, east, south, and west neighbouring squares, with the following restriction: if two opposite directions both have lines, then at least one of the other two directions has a line as well. In other words, it is forbidden for a square to consist of a straight line.

The objective of the game is to rotate each square, as many times as you like, such that for each square, if it has a line going in a compass direction (that is, north, east, south, or west), then it has a neighbour in that compass direction and that neighbour has a line going in the opposite compass direction. In other words, each edge in the grid should either have a line on both sides or neither side.

Your task is to determine whether a given grid has a solution.

The input consists of several test cases.

The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 12.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

• If the string is the single character x, then the square does not contain a line to any of its neighbours.
• Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

The input consists of several test cases.

The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 12.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

• If the string is the single character x, then the square does not contain a line to any of its neighbours.
• Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

3 3
NW NW x
NES NESW W
E W x
2 2
ES x
x N
0 0

SOLVABLE
UNSOLVABLE

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010100;
const int INF = 0x3f3f3f3f;
int n,m,tot;
struct Hash {
struct Node {int v; int id; Node *next;};
int mod;
Node *table[5555],memo[N];
void init() {
tot = 0;
mod = 5501;
memset(table,0,sizeof(table));
}
int operator [] (int x) {
int idx = x%mod;
for (Node *i = table[idx]; i ; i = i->next)
if (x==i->v) return i->id;
memo[tot] = (Node) {x,tot,table[idx]};
table[idx] = &memo[tot];
}
}hash;
char s[55][55];
int mat[55][55][2],f[2][N],*cur,*nex;
int tomin(int &a,int b) { if (a>b)a=b; }
int work() {
for (int i = 0; i < 2*n+1; i ++)
for (int j = 0; j < 2*m+1; j ++)
if (s[i][j]=='#') s[i][j] = '0';
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++) {
mat[i][j][0] = s[i*2+1][j*2+2]-'0';
mat[i][j][1] = s[i*2+2][j*2+1]-'0';
}
cur = f[0]; nex = f[1];
memset(f,INF,sizeof(f));
hash.init();
cur[hash[0]] = 0;

for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
for (int st = 0; st < tot; st ++) if (cur[st]!=INF) {
int v = hash.memo[st].v;
int a = v>>m>>m&3;
int b = v>>j>>j&3;

if (!a && !b) {
if (j!=m-1)
tomin(nex[hash[v^2<<m<<m^1<<j<<j]],cur[st]+mat[i][j][0]+mat[i][j][1]);
} else if (!a && b) {
tomin(nex[st],cur[st]+mat[i][j][1]);
if (j!=m-1)
tomin(nex[hash[v^b<<m<<m^b<<j<<j]],cur[st]+mat[i][j][0]);
} else if (a && !b) {
if (j!=m-1)
tomin(nex[st],cur[st]+mat[i][j][0]);
tomin(nex[hash[v^a<<m<<m^a<<j<<j]],cur[st]+mat[i][j][1]);
} else if (a && b) {
int k,cnt;
if (a==1 && b==1) {
for (k = j+1,cnt = 0; k < m; k ++) {
int vp = v>>k>>k&3;
if (vp==1) cnt ++;
else if (vp==2) cnt --;
if (cnt==-1) break;
}
tomin(nex[hash[v^a<<m<<m^b<<j<<j^3<<k<<k]],cur[st]);
} else if (a==2 && b==2) {
for (k = j-1,cnt = 0; k >= 0; k --) {
int vp = v>>k>>k&3;
if (vp==1) cnt ++;
else if (vp==2) cnt --;
if (cnt==1) break;
}
tomin(nex[hash[v^a<<m<<m^b<<j<<j^3<<k<<k]],cur[st]);
} else if (a==2 && b==1) {
tomin(nex[hash[v^a<<m<<m^b<<j<<j]],cur[st]);
} else if (a==1 && b==2) {
if (i==n-1 && j==m-1)
tomin(nex[hash[v^a<<m<<m^b<<j<<j]],cur[st]);
}
}
}
swap(cur,nex);
for (int k = 0; k < tot; k ++) nex[k] = INF;
}
}
return cur[0];
}
int main() {
int cas;
scanf("%d",&cas);
while (cas--) {
scanf("%d%d\n",&n,&m);
for (int i = 0; i < 2*n+1; i ++)
gets(s[i]);
printf("%d\n",work());
}
return 0;
}

1. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

2. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

3. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

4. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

5. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

6. 固定答案当然是亲人，你不觉得太绝对了吗？如果这个亲人并不亲，只是血缘上的亲，而在感情上反而是仇呢？宫斗剧里常有的桥段，而那个陌生人如果是个美丽的异性或者第一印象给人就是好的感觉呢？你又怎么选择？你说这有绝对固定的答案？理由也很好找，我就是看到陌生人，没看

7. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

8. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。