HDU 4796 Winter's Coming （插头DP）

AC 了。 一个地方写错，导致产生了多余的环！！！！！ 13年长沙的插头DP题。 //写了一下插头DP， WA到死，然后这题有天坑！！！！ //留个坑吧！ 记录下自己写的插头DP代码！ 当年写得很熟悉的插头DP现在都快忘记了。 已经AC

/* ***************

Author        :kuangbin

Created Time  :2014/9/8 19:22:58

File Name     :tmp.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXD = 15;

const int STATE = 1000010;

const int HASH = 10007;

int N,M;

int maze[24][MAXD];//-1禁止，-2左边，-3右边

int code[MAXD];

int ch[MAXD];

struct HASHMAP{

	int head[HASH],next[STATE],size;

	long long state[STATE];

	int f[STATE];

	void init(){

		size = 0;

		memset(head,-1,sizeof(head));

	}

	void push(long long st,int ans){

		int h = st%HASH;

		for(int i = head[h];i != -1;i = next[i])

			if(state[i] == st){

				f[i] = min(f[i],ans);

				return;

			}

		state[size] = st;

		f[size] = ans;

		next[size] = head[h];

		head[h] = size++;

	}

}hm[2];

void decode(int *code,int m,long long st){

	for(int i = m;i >= 0;i--){

		code[i] = st&7;

		st >>= 3;

	}

}

long long encode(int *code,int m){

	int cnt = 1;

	memset(ch,-1,sizeof(ch));

	ch[0] = 0;

	long long st = 0;

	for(int i = 0;i <= m;i++){

		if(ch[code[i]] == -1)ch[code[i]] = cnt++;

		code[i] = ch[code[i]];

		st <<= 3;

		st |= code[i];

	}

	return st;

}

void dpblank(int i,int j,int cur){

	int k,left,up;

	for(k = 0;k < hm[cur].size;k++){

		decode(code,M,hm[cur].state[k]);

		left = code[j-1];

		up = code[j];

		if(left && up){

			if(left == up){

				continue;//这种情况不能合并，否则会形成多余的环

				code[j-1] = code[j] = 0;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

			}

			else {

				code[j-1] = code[j] = 0;

				for(int t = 0;t <= M;t++)

					if(code[t] == up)

						code[t] = left;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

			}

		}

		else if(left || up){

			int t ;

			if(left) t = left;

			else t = up;

			if(i == N){

				int cc = 0;

				for(int p = 0;p < j-1;p++)

					if(code[p])

						cc++;

				if(cc == 0){

					code[j] = 0;

					code[j-1] = t;

					hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

				}

			}

			else if(maze[i+1][j] >= 0){

				code[j] = 0;

				code[j-1] = t;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

			}

			if(maze[i][j+1] >= 0){

				code[j-1] = 0;

				code[j] = t;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

			}

		}

		else {

			code[j-1] = code[j] = 0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]);

			if(i == N){

				int cc = 0;

				for(int p = 0;p < j-1;p++)

					if(code[p])

						cc++;

				if(cc == 0 && maze[i][j+1] >= 0){

					code[j] = code[j-1] = 13;

					hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

				}

			}

			else if(maze[i+1][j] >= 0 && maze[i][j+1] >= 0){

				code[j] = code[j-1] = 13;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]+maze[i][j]);

			}

		}

	}

}

void dpblock(int i,int j,int cur){

	int k = 0;

	for(int k = 0;k < hm[cur].size;k++){

		decode(code,M,hm[cur].state[k]);

		if(code[j] || code[j-1])continue;

		int cc = 0;

		for(int p = 0;p < j-1;p++)

			if(code[p])

				cc++;

		if(maze[i][j] == -2 && cc%2 == 0){

			code[j-1] = code[j] = 0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]);

		}

		else if(maze[i][j] == -3 && cc%2 == 1){

			code[j-1] = code[j] = 0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]);

		}

		else if(maze[i][j] == -1){

			code[j-1] = code[j] = 0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].f[k]);

		}

	}

}

char str[20];

void init(){

	memset(maze,-1,sizeof(maze));

	for(int i = 1;i <= N;i++){

		scanf("%s",str);

		for(int j = 1;j <= M;j++){

			if(str[j-1] == '#')maze[i][j] = -1;

			else if(str[j-1] == 'W')maze[i][j] = -2;

			else if(str[j-1] == 'L')maze[i][j] = -3;

			else maze[i][j] = str[j-1] - '0';

		}

	}

}

const int INF = 0x3f3f3f3f;

void solve(){

	int i,j,cur = 0;

	hm[cur].init();

	for(i = 1;i <= M;i++){

		if(maze[1][i] < 0)continue;

		for(j = 0;j <= M;j++){

			if(j == i)code[j] = 1;

			else code[j] = 0;

		}

		hm[cur].push(encode(code,M),0);

	}

	for(i = 1;i <= N;i++)

		for(j = 1;j <= M;j++){

			hm[cur^1].init();

			if(maze[i][j] >= 0)dpblank(i,j,cur);

			else dpblock(i,j,cur);

			cur ^= 1;

		}

	int ans = INF;

	for(i = 0;i < hm[cur].size;i++){

		decode(code,M,hm[cur].state[i]);

		int cc = 0;

		for(j = 1;j <= M;j++)

			if(code[j])

				cc++;

		if(cc == 1)ans = min(ans,hm[cur].f[i]);

	}

	if(ans == INF)ans = -1;

	printf("%d\n",ans);

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

	while(scanf("%d%d",&N,&M) == 2){

		init();

		solve();

	}

    return 0;

}