bfs（标记整个棋盘）

1004 四子连棋

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

数据范围及提示 Data Size & Hint

还有迭代加深搜的方法，有待探索。

#include<bits/stdc++.h>
#define rep(i , n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
char m[4][4];
int dir[4][2] = {{1 , 0},{-1 , 0},{0 , 1},{0, -1}};
struct node{
    char M[4][4];
    int dis ;
    char last;
    node(char m[4][4] , int d = 0 , char c = 'B')
    {
        rep(i , 4)
        {
            rep(j , 4)
            {
                M[i][j] = m[i][j];
            }
        }
        dis = d ;//移动步数
        last = c ;//标录上一次与哪个棋子进行了交换
    }
};

string con(char m[4][4])//比较移动后的棋盘与之前的棋盘是否相同与map<string , int>相结合结合
{
    string s = "";
    rep(i , 4)
    rep(j , 4)
    s += m[i][j];
    return s;
}

bool judge(char m[4][4])//判断是否有四子连棋
{
    rep(i , 4)
    {
        if(m[i][0] == m[i][1] && m[i][1] == m[i][2] && m[i][2] == m[i][3])
            return true ;
        if(m[0][i] == m[1][i] && m[1][i] == m[2][i] && m[2][i] == m[3][i])
            return true ;
    }
    if(m[0][0] == m[1][1] && m[1][1] == m[2][2] && m[2][2] == m[3][3])
        return true ;
    if(m[3][0] == m[2][1] && m[2][1] == m[1][2] && m[1][2] == m[0][3])
        return true ;
    return false ;
}
map<string , int>vis;

int main()
{
    rep(i , 4)
    rep(j , 4)
    cin >> m[i][j];
    queue<node>q;
    q.push(node(m , 0 , 'O'));
    vis[con(m)] = 1 ;
    while(!q.empty())
    {
        node t = q.front() ;
        q.pop() ;
        if(judge(t.M))
        {
            cout << t.dis <<endl ;
            return 0 ;
        }
        int x[2] , y[2];
        int num = -1 ;
        rep(i , 4)
        {
            rep(j , 4)
            {
                if(t.M[i][j] == 'O')
                {
                    x[++num] = i;
                    y[num] = j ;
                }
            }
        }
        rep(i , 2)
        {
            rep(j , 4)
            {
                int xx = x[i] + dir[j][0];
                int yy = y[i] + dir[j][1];
                char temp[4][4];
                rep(i , 4)
                rep(j , 4)
                temp[i][j] = t.M[i][j];
                if(xx >= 0 && xx < 4 && yy >= 0 && yy < 4 &&t.M[xx][yy]!='O' && t.M[xx][yy] != t.last) //空与空不移，不和上一次移过的一样
                {
                    temp[x[i]][y[i]] = temp[xx][yy];
                    temp[xx][yy] = 'O';
                }
                string s = con(temp);
                if(!vis[s])//移完过后是否与之前的棋盘相同
                {
                    vis[s] = 1 ;
                    q.push(node(temp , t.dis+1 , temp[x[i]][y[i]]));
                    if(judge(temp))
                    {
                        cout << t.dis+1 << endl;
                        return 0 ;
                    }
                }
            }
        }
    }

    return 0;
}