【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

思路

状压+迭代深搜

代码

#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;
}