2015
04-16

# Construct the Great Wall

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).



#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 state[STATE],f[STATE];
void push(int st,int ans){
int h = st%HASH;
if(st==state[i]){
f[i] = min(f[i], ans);
return ;
}
}
}
}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;
}


1. 所以嘛 我一直认为 我朝上广北深的教师每4年应该去支边一年 不愿意的开除 不要成天骂骂咧咧的说总理不好 工资不高 你见过哪个人一年能放3个月假还拿13个月工资的 退休待遇还那么好 逢年过节还发饺子皮的 老师就应该去乡下锻炼一下 不要搞的中国教育***全部

2. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

3. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

4. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

5. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

6. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

7. 了解到鲜为人知的东西了，网上就一个日报打了几个大标题和反革命内容，能看出他们不想下台，要吧权利紧紧握着。这事件真的很少人知道了，年轻一辈更没有人知道，我是1989年12月出生的，学校的历史和政治都没有提及那年的恶行。

9. #include <cstdio>

int main() {