Code[VS] 1004 四子连棋

【题意】

    给定4*4的棋盘，每个位置上为"B"、"W"或" "，表示黑棋、白棋或空格。定义目标棋局为有一行、一列或一条对角线上有相同颜色的四个子。黑白交替下，开始时任意一方先下，求最少多少步能达到目标棋局。

【分析】

首先定义变量：

基本   q（1）wt[2][2]记录空格位置  

        （2）int p[4][4]记录值，黑棋存1，白棋存2，空格存0

哈希表 hash（1）long long data，存棋局的值，就是转化为10进制后存储

           （2）next，邻接表存下个位

           （3）has，这个位置的个数

      LMT=100000009;

       Hd[LMT]存哈希表头

    本题要求最小步数达到目标棋局，可以用广搜，但是广搜容易爆空间，而且不大好写，那就用迭代加深搜索好了。

迭代加深搜索的实现

Int check(void)
{
    横排判定；
    纵列判定；
    左上-右下对角线判定；//对角线上的（i，j）满足i=j
    右上-左下对角线判定；//对角线上的（i，j）满足i+j=4+1=5
}
 
Void swap（&I,&j）
{
    I^=j^=i^=j； //怎么写都一样的啦
}
 
Int update(int u,int tag) //把插入、查找、删除给放到一个过程，因为很多部分都相同
{
    Int key=u%LM;   //得到属于的集合
    for (intk=hd[key];k;k=hash[k].next)  //枚举数据
        if(hash[k].data==u)    //若等于
            if(typ==2) return hash[k].has;//若为查找过程返回has
            else
            {
                hash[k].has^=1;  //has的状态改变
                return1;   //直接退出
            }
    if (typ^2) //如果不是查找过程，则说明是插入过程，因为删除过程必定在上面完成了
    {
        hash[++tot].data=u;
        hash[tot].has=1;
        hash[tot].next=hd[key];
        hd[key]=tot;            //插入
    }
    return 0;   //返回0，满足查找的找不到
}
 
Int can(int x,int y) //判定坐标满不满足
{
    Return x+1&&x<4&&y+1&&y<4；//0<=x,y<=3
}
 
Int DFS(int dep,int lmt,int turn) //dep存当前第几步，lmt存深度，turn存哪一方
{
    if (dep==lmt)return check(); //若到达了目标深度则判断行不行
    long longgt=get();
    update(gt,0);   //哈希表中插入当前状态
    int d=0; //标记
    for (inti=0;!d&&i<2;i++)   //枚举哪个空格移动
        for (intj=0;!d&&j<4;j++)   //枚举往哪走
            if(can(p.wt[i][0]+dx[j],p.wt[i][1]+dy[j],turn)) //若可以移动
            {
                intx=p.wt[i][0]+dx[j],y=p.wt[i][1]+dy[j];  //x，y记录移动后的位
                swap(p.p[p.wt[i][0]][p.wt[i][1]],p.p[x][y]);
                p.wt[i][0]+=dx[j];
                p.wt[i][1]+=dy[j];  //交换
                if(!update(get(),2)) d|=DFS(dep+1,lmt,(turn-1^1)+1);
                                            //如果没有这个状态则继续DFS
                p.wt[i][0]-=dx[j];
                p.wt[i][1]-=dy[j];
                swap(p.p[p.wt[i][0]][p.wt[i][1]],p.p[x][y]);//还原
            }
    update(gt,0);  //从哈希表中删除当前状态
    return d;   //返回标记
}
 
Int main(void)
{
    ……
 
    For (cnt=0;!DFS(0,cnt,0)&&!DFS(0,cnt,1);cnt++);
    Printf("%d\n",cnt);
 
    Return 0;
}

代码比较长，所以说这道题是神级的水题也差不多了……

【代码】

#include <cstdio>
#include <cstring>
#include <cstdlib>
 
using namespace std;
 
const int LM=10000009;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
 
struct A
{
    int p[4][6];
    int wt[2][2];
}p;
struct H
{
    long longdata;
    int next,has;
}hash[3000000];
int hd[LM],tot;
int cnt;
 
int check(void)
{
    int d;
    for (inti=0;i<4;i++)
    {
        d=1;
        for (intj=1;j<4;j++)
            if(p.p[i][j]^p.p[i][0]) {d=0;break;}
        if (d)return 1;
    }
    for (inti=0;i<4;i++)
    {
        d=1;
        for (intj=1;j<4;j++)
            if(p.p[j][i]^p.p[0][i]) {d=0;break;}
        if (d)return 1;
    }
    d=1;
    for (inti=1;i<4;i++)
        if(p.p[0][0]^p.p[i][i]) {d=0;break;}
    if (d) return1;
    d=1;
    for (inti=1;i<4;i++)
        if(p.p[0][4]^p.p[i][4-i]) {d=0;break;}
    return d;
}
 
long long get(void)
{
    long longsum=0,mtp=1;
    for (inti=3;i+1;i--)
        for (intj=3;j+1;j--)
            sum+=mtp*p.p[i][j],mtp*=10;
    return sum;
}
 
int update(long long u,int typ)
{
    intkey=(int)(u%LM);
    for (intk=hd[key];k;k=hash[k].next)
        if(hash[k].data==u)
            if(typ==2)
                if(hash[k].has) return 1; else;
            else
            {
                hash[k].has^=1;
                return1;
            }
    if (typ^2)
    {
        hash[++tot].data=u;
        hash[tot].has=1;
        hash[tot].next=hd[key];
        hd[key]=tot;
    }
    return 0;
}
 
int can(int x,int y,int turn)
{
    returnx+1&&x<4&&y+1&&y<4&&p.p[x][y]==turn;
}  
 
void swap(int &i,int &j)
{
    i^=j^=i^=j;
}
 
int DFS(int dep,int lmt,int turn)
{
    if (dep==lmt)return check();
    long longgt=get();
    update(gt,1);
    int d=0;
    for (inti=0;!d&&i<2;i++)
        for (intj=0;!d&&j<4;j++)
            if(can(p.wt[i][0]+dx[j],p.wt[i][1]+dy[j],turn))
            {
                intx=p.wt[i][0]+dx[j],y=p.wt[i][1]+dy[j];
                swap(p.p[p.wt[i][0]][p.wt[i][1]],p.p[x][y]);
                p.wt[i][0]+=dx[j];
                p.wt[i][1]+=dy[j];
                if(!update(get(),2)) d|=DFS(dep+1,lmt,(turn-1^1)+1);
                p.wt[i][0]-=dx[j];
                p.wt[i][1]-=dy[j];
                swap(p.p[p.wt[i][0]][p.wt[i][1]],p.p[x][y]);
            }
    update(gt,0);
    return d;
}
 
int main(void)
{
    int c=0; chars;
    for (inti=0;i<4;i++)
    {
        for (intj=0;j<4;j++)
        {
            scanf("%c",&s);
            p.p[i][j]=(s=='B'?2:s=='W'?1:0);
        }
        scanf("\n");
    }
    for (inti=0;i<4;i++)
        for (intj=0;j<4;j++)
            if(!p.p[i][j]) p.wt[c][0]=i,p.wt[c++][1]=j;
   
    for(cnt=0;!DFS(0,cnt,1)&&!DFS(0,cnt,2);cnt++);
    printf("%d\n",cnt);
   
    return 0;
}

【小结】

（1）在发现审错题或方法不对时，要学会给程序进行调整，而不应该前功尽弃，完全否定。

（2）程序的共用思想，几个类似的过程放到一个过程去完成，达到化简的效果

（3）当用广搜发现空间很大或无法估计空间时，可以考虑迭代加深搜索。

Code[VS] 1004 四子连棋

原文：http://blog.csdn.net/u013598409/article/details/43924465