首页 > 数据结构 > Hash表 > HDU 4113-Construct the Great Wall-动态规划-[解题报告]HOJ
2015
04-16

HDU 4113-Construct the Great Wall-动态规划-[解题报告]HOJ

Construct the Great Wall

问题描述 :

Break the Chocolate

A defensive wall is a fortification used to protect a city or settlement from potential aggressors. From ancient to modern times, they were used to enclose settlements.
Generally, these are referred to as city walls or town walls.
Even though, our ancestors decided to build a Great Wall to protect the northern borders of the Chinese Empire against invasion by various nomadic groups.
The map is given as an rectangle area of size N × M. Each grid is an empty area, a city or an enemy. The Great Wall is a simple polygon build alone the edge of the grids, enclosing all the cities and keeping all the enemies out.
The Great Wall is not easy to build, so we should make the Great Wall as short as possible. Now it is your job to calculate the length of the shortest Great Wall so that it can protect all the cities from the enemies.

输入:

The first line contains an integer T(1 <= T<= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains two integer H,W(1 <= H,W <= 8), indicating the number of rows and columns of the map.
The followingH lines containsW chars, indicating the map. ‘o’ represents a city, ‘.’ represents a empty area and ‘x’ represents an enemy.
You can assume that there will be at least one city on the map.

输出:

The first line contains an integer T(1 <= T<= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains two integer H,W(1 <= H,W <= 8), indicating the number of rows and columns of the map.
The followingH lines containsW chars, indicating the map. ‘o’ represents a city, ‘.’ represents a empty area and ‘x’ represents an enemy.
You can assume that there will be at least one city on the map.

样例输入:

3
3 3
.o.
.x.
o.o
4 4
....
.ox.
.xo.
....
5 5
.ooo.
.x...
..xoo
x.xoo
.ox.x

样例输出:

Case #1: 14
Case #2: -1
Case #3: 28
Hint
A simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments. The solution for the first test case in sample is shown in Figure 1. There is no solution for the second test case because no matter how you build the Great Wall, it will always intersects with itself. (Figure 2).
Break the Chocolate

好久没做插头dp的样子,一开始以为这题是插头,状压,插头,状压,插头,状压,插头,状压,无限对又错。

昨天看到的这题。

百度之后发现没有人发题解,hust也没,hdu也没discuss。。。在acm-icpc信息站发现难得的一篇题解。不过看到是插头二字之后,代码由于风格太不一样就没看了,自己想了好久,想通了。然后就等到今天才码。。。。

 

如果把点看成网格,那就可以实现,没有公共点公共边等限定条件,也显然是插头dp的最短单回路的模型。这是本题的一个难点(当时想到这样是因为,题目要求计算最短周长,显然这样建模便于求解)

另一个难点是如何保证那些OOXX在该在的位置,即题目所要求,O在单回路内部,X在单回路外部。我的做法是标记,加多一维01表示当前交点的左上角格子是否在内部。转移过程注意判断后续状态可否行即可。

这题要括号匹配,显然要用哈希表而不用数组。。。

虽然折腾时间挺久,但是1A的感觉还是不错的。

 

建议画图(其实所有插头dp都建议画图,便于分析,也不会占着电脑坑队友)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-8
#define ll long long
#define maxm 51000


#define STATE 510000
#define HASH 10007
#define maxd 15

int n,m;
char maze[maxd][maxd];
int code[maxd];
struct HASHMAP{
	int head[HASH],nxt[STATE],sz;
	int state[STATE],f[STATE];
	void clear(){sz=0;memset(head,-1,sizeof(head));}
	void push(int st,int ans){
		int h = st%HASH;
		for(int i=head[h];i!=-1;i=nxt[i]){
			if(st==state[i]){
				f[i] = min(f[i], ans);
				return ;
			}
		}
		state[sz]=st, f[sz]=ans, nxt[sz]=head[h];
		head[h]=sz++;
	}
}hm[2][2];
void decode(int st){
	for(int i=0;i<=m;++i) code[i] = st&3, st>>=2;
}
int encode(){
	int ret=0;
	for(int i=m;i>=0;--i) ret = ret<<2|code[i];
	return ret;
}
bool jud(int i,int j,int in){
	if(maze[i][j]=='o') return in;
	if(maze[i][j]=='x') return !in;
	return true;
}
int edx,edy;
int ans;
void dp(int i,int j,int cur,int in){
	int xo = (1<<(j*2));
	int ox = (2<<(j*2));
	int oo = xo|ox;
	int mv = (j==m?2:0);
	for(int k=0;k<hm[cur][in].sz;++k){
		decode(hm[cur][in].state[k]);
		int left = code[j-1];
		int up = code[j];
		if(left && up){
			if(left==2 && up==1){
				if(i>=edx+1 && j>=edy+1){
					int to = hm[cur][in].state[k] ^ (ox>>2) ^ (xo);
					if(to==0) ans = min(ans, hm[cur][in].f[k]+1);
				}
				continue;
			}
			if(left==1 && up==1){
				for(int jj=j-1,c=0;jj>=0;--jj){
					if(code[jj]==1)++c;
					if(code[jj]==2)--c;
					if(c==0){code[jj]^=3;break;}
				}
				code[j-1]=code[j]=0;
			}
			if(left==2 && up==2){
				for(int jj=j,c=0;jj<=m;++jj){
					if(code[jj]==2)++c;
					if(code[jj]==1)--c;
					if(c==0){code[jj]^=3;break;}
				}
				code[j-1]=code[j]=0;
			}
			if(left==1 && up==2){
				code[j-1]=code[j]=0;
			}
			if(jud(i-1,j,in^1))
				hm[cur^1][in^1].push(encode()<<mv, hm[cur][in].f[k]+1);
		}else if(left || up){
			int in2 = in;
			if(up) in2^=1;
			int tmp = left | up;
			code[j-1]=tmp, code[j]=0;
			if(i+1<=n)
				if(jud(i-1,j,in2) && jud(i,j-1,!in2) && jud(i,j,in2))
					hm[cur^1][in2].push(encode()<<mv, hm[cur][in].f[k]+1);
			code[j-1]=0, code[j]=tmp;
			if(j+1<=m)
				if(jud(i-1,j,in2) && jud(i,j-1,!in2) && jud(i,j,!in2))
					hm[cur^1][in2].push(encode()<<mv, hm[cur][in].f[k]+1);
		}else {
			if(jud(i-1,j,in) && jud(i,j-1,in) && jud(i,j,in))
				hm[cur^1][in].push(hm[cur][in].state[k]<<mv, hm[cur][in].f[k]);
			code[j-1]=2, code[j]=1;
			if(i+1<=n && j+1<=m)
				if(jud(i-1,j,in) && jud(i,j-1,in) && jud(i,j,!in))
					hm[cur^1][in].push(encode()<<mv, hm[cur][in].f[k]+1);
		}
	}
}
int solve(){
	int cur=0;
	hm[0][0].clear();
	hm[0][1].clear();
	hm[0][0].push(0,0);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(maze[i][j]=='o') edx=i,edy=j;
	ans=inf;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			hm[cur^1][0].clear();
			hm[cur^1][1].clear();
			dp(i,j,cur,0);
			dp(i,j,cur,1);
			cur^=1;
		}
	}
	if(ans==inf) return -1;
	return ans;
}
int main(){
	int t,ca=0;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(maze,0,sizeof(maze));
		for(int i=1;i<=n;++i) scanf("%s",maze[i]+1);
		++n,++m;
		for(int i=0;i<=n;++i) maze[i][0]=maze[i][m]='.';
		for(int j=0;j<=m;++j) maze[0][j]=maze[n][j]='.';
		printf("Case #%d: %d\n",++ca, solve());
	}
	return 0;
}

 

参考:http://www.cnblogs.com/nextbin/p/4082001.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }