Codevs p1004 四子连棋

时间：2022-04-11 12:32:49

                      四子连棋

题目描述 Description

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

● ○ ●  
○ ● ○ ●
● ○ ● ○
○ ● ○  
输入描述 Input Description
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。









输出描述 Output Description






用最少的步数移动到目标棋局的步数。











样例输入 Sample Input






BWBO
WBWB
BWBW
WBWO











样例输出 Sample Output






5











数据范围及提示 Data Size & Hint






hi



思路分析： bfs+hash判重，记录每次走过的棋局，进行每条直线与对角线的判断（类似于八皇后的判断），记录下一步该走黑棋还是白棋。



我是看的hzw神犇的blog才会的，程序基本上是理解了照搬过来的，不建议看。hzw神犇的题解-->http://hzwer.com/848.html

程序：





 #include <iostream>

 using namespace std;

 struct data

 {

     int map[][];

 }dt[];

 int next[]={,};

 int step[];

 bool haxi[];

 int x1[]={,,,-},

     y1[]={,-,,};

 int t=,w=,f=;

 int hash()

 {

     int k=,s=;

     for (int i=;i<=;i++)

       for (int j=;j<=;j++)

         {

             s+=dt[w].map[i][j]*k;

             k*=;

         }

     s%=;

     if (!haxi[s])

       {

           haxi[s]=;

           return ;

       }

     return ;

 }

 bool pd4l(int a1,int b1,int c,int d)

 {

     if (a1!=b1||b1!=c||c!=d||a1!=d) return ;

     return ;

 }

 bool fnis()

 {

     for (int i=;i<=;i++)

       {

           if (pd4l(dt[w].map[i][],dt[w].map[i][],dt[w].map[i][],dt[w].map[i][])) return ;

           if (pd4l(dt[w].map[][i],dt[w].map[][i],dt[w].map[][i],dt[w].map[][i])) return ;

       }

     if (pd4l(dt[w].map[][],dt[w].map[][],dt[w].map[][],dt[w].map[][])) return ;

     if (pd4l(dt[w].map[][],dt[w].map[][],dt[w].map[][],dt[w].map[][])) return ;

     return ;

 }

 void excg(int &a,int &b)

 {  int t;

    t=a;

    a=b;

    b=t;

 }

 bool pd(int x,int y)

 {   int k;

     k=next[t];

     if (x>||x==||y>||y==) return ;

     else if (dt[t].map[x][y]==k) return ;

     return ;

 }

 void move(int x,int y)

 {

     int p,q;

     for (int i=;i<;i++)

       {

           p=x1[i]+x;

           q=y1[i]+y;

           if (pd(p,q))

             {

                 for (int j=;j<=;j++)

                   for (int k=;k<=;k++)

                     dt[w].map[j][k]=dt[t].map[j][k];

                 excg(dt[w].map[p][q],dt[w].map[x][y]);

                 step[w]=step[t]+;

                 if (fnis()) {cout<<step[w]; f=;return;}

                 if (hash())

                   {

                   if (next[t]==) next[w++]=;

                   if (next[t]==) next[w++]=;

                   }

             }

       }

 }

 void search()

 {

     while (t<w)

       {

           for (int i=;i<=;i++)

             for (int j=;j<=;j++)

             {

               if (dt[t].map[i][j]==)

                  move(i,j);

               if (f==) return;

           }

           t++;

       }

 }

 int main()

 {

     char x;

     for (int i=;i<=;i++)

       for (int j=;j<=;j++)

         {

             cin>>x;

             if (x=='W') {dt[].map[i][j]=dt[].map[i][j]=;}

             if (x=='B') {dt[].map[i][j]=dt[].map[i][j]=;}

             // if (x=='O') {dt[0].map[i][j]=dt[1].map[i][j]=0;}

         }

      search();

      return ;

 }




99％相同，题解是条不归路。







相关文章