【codevs】1004 四子连棋

地址

http://codevs.cn/problem/1004/

题目

题目描述 Description 在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜线),这样的状态为目标棋局。

● ○ ●
○ ● ○ ● ● ○ ● ○ ○ ● ○

输入描述 Input Description 从文件中读入一个4*4的初始棋局,黑棋子用B表示,白棋子用W表示,空格地带用O表示。 输出描述 Output Description 用最少的步数移动到目标棋局的步数。

样例输入 Sample Input BWBO WBWB BWBW WBWO 样例输出 Sample Output 5

思路

状压+迭代深搜

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int ans=-1,deep_mx;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

int get_st(int st,int x,int y)
{
if(x<0||x>3||y<0||y>3) return -1;
for(int i=0,mx=(3-x)*4+(3-y);i<mx;i++)
st/=3;
return st%3;
}
int get_sum(int x,int y)
{
int ret=1;
for(int i=0,mx=(3-x)*4+(3-y);i<mx;i++)
ret*=3;
return ret;
}
bool check(int st)
{
int ok=1;
for(int i=0;i<4;i++)
{
ok=1;
for(int j=1;j<4&&ok;j++)
if(get_st(st,i,0)!=get_st(st,i,j))
ok=0;
if(ok) return 1;
ok=1;
for(int j=1;j<4&&ok;j++)
if(get_st(st,0,i)!=get_st(st,j,i))
ok=0;
if(ok) return 1;
}
ok=1;
for(int i=1;i<4&&ok;i++)
if(get_st(st,i,i)!=get_st(st,0,0))
ok=0;
if(ok) return 1;
ok=1;
for(int i=1;i<4&&ok;i++)
if(get_st(st,i,3-i)!=get_st(st,0,3))
ok=0;
if(ok) return 1;
return 0;
}
void dfs(int st,int ff,int d)
{
if(ans!=-1||d>=deep_mx) return;
if(check(st)) {ans=d;return;}
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
int now=get_st(st,i,j);
if(now!=0) continue;
for(int k=0;k<4;k++)
{
int nx=i+dx[k],ny=j+dy[k];
if(get_st(st,nx,ny)==ff)
dfs(st-get_sum(nx,ny)*ff+get_sum(i,j)*ff,3-ff,d+1);
}
}
}


int main(void)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
char ss[50];
int st=0;
for(int i=0;i<4;i++)
scanf("%s",ss+i*4);
for(int i=0;i<16;i++)
if(ss[i]=='O')
st=st*3+0;
else if(ss[i]=='B')
st=st*3+1;
else
st=st*3+2;
for(deep_mx=1;deep_mx<=50;deep_mx++)
for(int j=1;j<3&&ans==-1;j++)
dfs(st,j,0);
printf("%d\n",ans);
return 0;
}