【codevs】1004 四子连棋解题报告

论坛 › 期权论坛 › 脚本     
匿名网站用户   2020-12-19 22:00   11   0

原题链接：http://codevs.cn/problem/1004/



这道题，由于是求最小的深度，所以首先排除dfs（除非你有判重剪枝设置深度上限的小技巧，不然不建议使用dfs）。bfs可以很快得到思路，但是代码实现却十分繁琐。

首先要考虑如何将图加入队列。有一个很简单的方法就是二进制，一共有16个点，每个点只有0或1两种情况（感谢Claris大佬的指导），而int的上限为2^32，恰好可以储存所有的点，于是就可以得到将图转化为数字的函数。

int cta(char b[5][5])
{
   char k;
   int a=0;
   bool f=true;
   for(int i=1;i<=4;i++){
   for(int j=1;j<=4;j++){
      k=b[i][j];
      if(k=='O')k='W';
      if(k=='B'){a<<=1;a+=1;}
      if(k=='W'){a<<=1;}
   }
  }
  return a;
}

但是这样做还不够，还需要另外一个队列用于存放当前位置两个空位的位置，深度，以及轮到哪一方下棋。

然后考虑如何判断是否满足四子连棋，这个很容易实现，这里就不做过多分析。

bool check()
{
   char c[5][5];
   memset(c,0,sizeof(c));
   int a=q[h],m=q1[h][0],n=q1[h][1];
   for(int i=16;i>0;i--){
      if(a&1)i%4?(c[i/4+1][i%4]='B'):(c[i/4][4]='B');
      else i%4?(c[i/4+1][i%4]='W'):(c[i/4][4]='W');
      a>>=1;
   }
   m%4?(c[m/4+1][m%4]='O'):(c[m/4][4]='O');
   n%4?(c[n/4+1][n%4]='O'):(c[n/4][4]='O');
   //恢复图
   /*for(int i=1;i<=4;i++){
    for(int j=1;j<=4;j++){
        cout<<c[i][j];
    }
    cout<<endl;
   }
   cout<<endl;*/
   if(c[1][1]==c[2][2]&&c[2][2]==c[3][3]&&c[3][3]==c[4][4])return true;
   if(c[1][4]==c[2][3]&&c[2][3]==c[3][2]&&c[3][2]==c[4][1])return true;
   for(int i=1;i<=4;i++){
      if(c[i][1]==c[i][2]&&c[i][3]==c[i][4]&&c[i][2]==c[i][3])return true;
      if(c[1][i]==c[2][i]&&c[2][i]==c[3][i]&&c[3][i]==c[4][i])return true;
   }//判断连棋
   return false;

}
还有一个入队操作。
void push(int a,int x,int y,int d,int f){
    q[++t]=a;
    q1[t][0]=x;q1[t][1]=y;q1[t][2]=d+1;q1[t][3]=!f;
    //a为图，x，y分别表示两个空位，d为上一个深度，f为上一步走的黑白子
}

以及出队操作。（p函数是用来简化代码的，不然代码过于冗长）

void p(int x1,int y1,int n,int f,char c[5][5]){
    if(!f&&c[y1-1][x1]=='W'&&y1-1>0){
        swap(c[y1][x1],c[y1-1][x1]);
        push(cta(c),(y1-2)*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1-1][x1]);
    }
    if(!f&&c[y1+1][x1]=='W'&&y1+1<=4){
        swap(c[y1][x1],c[y1+1][x1]);
        push(cta(c),y1*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1+1][x1]);
    }
    if(!f&&c[y1][x1-1]=='W'&&x1-1>0){
        swap(c[y1][x1],c[y1][x1-1]);
        push(cta(c),(y1-1)*4+x1-1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1-1]);
    }
    if(!f&&c[y1][x1+1]=='W'&&x1+1<=4){
        swap(c[y1][x1],c[y1][x1+1]);
        push(cta(c),(y1-1)*4+x1+1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1+1]);
    }


    if(f&&c[y1-1][x1]=='B'&&y1-1>0){
        swap(c[y1][x1],c[y1-1][x1]);
        push(cta(c),x1+4*(y1-2),n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1-1][x1]);
    }
    if(f&&c[y1+1][x1]=='B'&&y1+1<=4){
        swap(c[y1][x1],c[y1+1][x1]);
        push(cta(c),y1*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1+1][x1]);
    }
    if(f&&c[y1][x1-1]=='B'&&x1-1>0){
        swap(c[y1][x1],c[y1][x1-1]);
        push(cta(c),(y1-1)*4+x1-1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1-1]);
    }
    if(f&&c[y1][x1+1]=='B'&&x1+1<=4){
        swap(c[y1][x1],c[y1][x1+1]);
        push(cta(c),(y1-1)*4+x1+1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1+1]);
    }
}

void pop()
{
    char c[5][5];
    memset(c,0,sizeof(c));
    int a=q[h],m=q1[h][0],n=q1[h][1];
    for(int i=16;i>0;i--){
        if(a&1)i%4?(c[i/4+1][i%4]='B'):(c[i/4][4]='B');
        else i%4?(c[i/4+1][i%4]='W'):(c[i/4][4]='W');
        a>>=1;
    }
    m%4?(c[m/4+1][m%4]='O'):(c[m/4][4]='O');
    n%4?(c[n/4+1][n%4]='O'):(c[n/4][4]='O');
    int y1=m%4?m/4+1:m/4,x1=m%4?m%4:4,y2=n%4?n/4+1:n/4,x2=n%4?n%4:4;
    p(x1,y1,(y2-1)*4+x2,q1[h][3],c);
    p(x2,y2,(y1-1)*4+x1,q1[h][3],c);
    h++;
}

以上函数包含了队列所有的操作，补充一个主函数程序就算完成了。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int q[100009],q1[100009][4];
int h=1,t=0;

int cta(char b[5][5])
{
   char k;
   int a=0;
   bool f=true;
   for(int i=1;i<=4;i++){
   for(int j=1;j<=4;j++){
      k=b[i][j];
      if(k=='O')k='W';
      if(k=='B'){a<<=1;a+=1;}
      if(k=='W'){a<<=1;}
   }
  }
  return a;
}

void push(int a,int x,int y,int d,int f){
    q[++t]=a;
    q1[t][0]=x;q1[t][1]=y;q1[t][2]=d+1;q1[t][3]=!f;
    //a为图，x，y分别表示两个空位，d为上一个深度，f为上一步走的黑白子
}
bool check()
{
   char c[5][5];
   memset(c,0,sizeof(c));
   int a=q[h],m=q1[h][0],n=q1[h][1];
   for(int i=16;i>0;i--){
      if(a&1)i%4?(c[i/4+1][i%4]='B'):(c[i/4][4]='B');
      else i%4?(c[i/4+1][i%4]='W'):(c[i/4][4]='W');
      a>>=1;
   }
   m%4?(c[m/4+1][m%4]='O'):(c[m/4][4]='O');
   n%4?(c[n/4+1][n%4]='O'):(c[n/4][4]='O');
   //恢复图
   /*for(int i=1;i<=4;i++){
    for(int j=1;j<=4;j++){
        cout<<c[i][j];
    }
    cout<<endl;
   }
   cout<<endl;*/
   if(c[1][1]==c[2][2]&&c[2][2]==c[3][3]&&c[3][3]==c[4][4])return true;
   if(c[1][4]==c[2][3]&&c[2][3]==c[3][2]&&c[3][2]==c[4][1])return true;
   for(int i=1;i<=4;i++){
      if(c[i][1]==c[i][2]&&c[i][3]==c[i][4]&&c[i][2]==c[i][3])return true;
      if(c[1][i]==c[2][i]&&c[2][i]==c[3][i]&&c[3][i]==c[4][i])return true;
   }//判断连棋
   return false;

}
void p(int x1,int y1,int n,int f,char c[5][5]){
    if(!f&&c[y1-1][x1]=='W'&&y1-1>0){
        swap(c[y1][x1],c[y1-1][x1]);
        push(cta(c),(y1-2)*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1-1][x1]);
    }
    if(!f&&c[y1+1][x1]=='W'&&y1+1<=4){
        swap(c[y1][x1],c[y1+1][x1]);
        push(cta(c),y1*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1+1][x1]);
    }
    if(!f&&c[y1][x1-1]=='W'&&x1-1>0){
        swap(c[y1][x1],c[y1][x1-1]);
        push(cta(c),(y1-1)*4+x1-1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1-1]);
    }
    if(!f&&c[y1][x1+1]=='W'&&x1+1<=4){
        swap(c[y1][x1],c[y1][x1+1]);
        push(cta(c),(y1-1)*4+x1+1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1+1]);
    }


    if(f&&c[y1-1][x1]=='B'&&y1-1>0){
        swap(c[y1][x1],c[y1-1][x1]);
        push(cta(c),x1+4*(y1-2),n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1-1][x1]);
    }
    if(f&&c[y1+1][x1]=='B'&&y1+1<=4){
        swap(c[y1][x1],c[y1+1][x1]);
        push(cta(c),y1*4+x1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1+1][x1]);
    }
    if(f&&c[y1][x1-1]=='B'&&x1-1>0){
        swap(c[y1][x1],c[y1][x1-1]);
        push(cta(c),(y1-1)*4+x1-1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1-1]);
    }
    if(f&&c[y1][x1+1]=='B'&&x1+1<=4){
        swap(c[y1][x1],c[y1][x1+1]);
        push(cta(c),(y1-1)*4+x1+1,n,q1[h][2],q1[h][3]);
        swap(c[y1][x1],c[y1][x1+1]);
    }
}

void pop()
{
    char c[5][5];
    memset(c,0,sizeof(c));
    int a=q[h],m=q1[h][0],n=q1[h][1];
    for(int i=16;i>0;i--){
        if(a&1)i%4?(c[i/4+1][i%4]='B'):(c[i/4][4]='B');
        else i%4?(c[i/4+1][i%4]='W'):(c[i/4][4]='W');
        a>>=1;
    }
    m%4?(c[m/4+1][m%4]='O'):(c[m/4][4]='O');
    n%4?(c[n/4+1][n%4]='O'):(c[n/4][4]='O');
    int y1=m%4?m/4+1:m/4,x1=m%4?m%4:4,y2=n%4?n/4+1:n/4,x2=n%4?n%4:4;
    p(x1,y1,(y2-1)*4+x2,q1[h][3],c);
    p(x2,y2,(y1-1)*4+x1,q1[h][3],c);
    h++;
}


int main()
{
   char c[5][5];
   int a=0;
   bool f=false;
   for(int i=1;i<=4;i++){
      for(int j=1;j<=4;j++){
         cin>>c[i][j];
      }
   }
   a=cta(c);
   for(int i=1;i<=4;i++){
    for(int j=1;j<=4;j++){
        if(c[i][j]=='O'&&!f){
            q1[1][0]=(i-1)*4+j;
            f=!f;
            continue;
        }
        if(c[i][j]=='O'&&f){
            q1[1][1]=(i-1)*4+j;
            goto qwq;
        }
    }
   }
   qwq:
   q[1]=a;q1[1][2]=0;q1[1][3]=0;
   t++;
   q[2]=q[1];q1[2][0]=q1[1][0];q1[2][1]=q1[1][1];q1[2][3]=1;
   t++;
   //q1[i][0,1]表示空格位置，q1[i][2]表示深度，q1[i][3]表示目前哪方下棋。
   while(!check()){
      pop();
   }
   printf("%d",q1[h][2]);
   return 0;
}


回复
分享到 :
0 人收藏
返回列表
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

16级独孤
匿名网站用户

积分:1136255
帖子:227251
精华:0
+ 关注 私信
期权论坛 期权论坛
期权网络科技版权所有
关于我们
联系我们
加入我们
反馈问题
免责声明
积分充值
统一社会信用代码
积分规则
网站地图
爱文库
下属网站
官方
新浪微博
微信公众号
◆
下载
表情包
App下载
期权论坛 期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.

发布
内容

下载期权论坛手机APP