codevs1004 四子连棋

题目描述 Description

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

const int maxn = ;

struct member{

    int last,step;

    int board[][];//[y][x]

};

member first,q[maxn];

int tot;

int dx[] = {,-,,};

int dy[] = {-,,,};

bool judge(member temp){

    int r1 = ,r2 = ;

    for(r1 = ;r1 <= ;r1++){

        bool sign = true;

        for(r2 = ;r2 <= ;r2++){

            if(temp.board[r1][r2] != temp.board[r1][r2+]) sign = false;

        }

        if(sign) return true;

    }

    for(r1 = ;r1 <= ;r1++){

        bool sign = true;

        for(r2 = ;r2 <= ;r2++){

            if(temp.board[r2][r1] != temp.board[r2+][r1]) sign = false;

        }

        if(sign) return true;

    }

    if(temp.board[][] == temp.board[][] && temp.board[][] == temp.board[][] && temp.board[][] == temp.board[][]) return true;

    if(temp.board[][] == temp.board[][] && temp.board[][] == temp.board[][] && temp.board[][] == temp.board[][]) return true;

    return false;

}

int bfs(){

    int h = ,t = ,nx,ny;

    member tailer;

    while(h <= t){

        if(judge(q[h])) return q[h].step;

        int f1 = ,f2 = ,ya,xa,yb,xb,sign = ;

        for(f1 = ;f1 <= ;f1++){

            for(f2 = ;f2 <= ;f2++){

                if(q[h].board[f1][f2] == ){

                    if(sign == ){

                        sign = ;

                        ya = f1;

                        xa = f2;

                    }else if(sign == ){

                        yb = f1;

                        xb = f2;

                    }

                }

            }

        }

        f1 = f2 = ;

        for(f1 = ;f1 < ;f1++){

            nx = xa + dx[f1];

            ny = ya + dy[f1];

            if(nx <=  && nx >=  && ny <= && ny >=  && q[h].board[ny][nx] != q[h].last){

                t++;

                tailer = q[h];

                tailer.last = tailer.board[ny][nx];

                swap(tailer.board[ny][nx],tailer.board[ny - dy[f1]][nx - dx[f1]]);

                tailer.step++;

                q[t] = tailer;

            }

            nx = xb + dx[f1];

            ny = yb + dy[f1];

            if(nx <=  && nx >=  && ny <= && ny >=  && q[h].board[ny][nx] != q[h].last){

                t++;

                tailer = q[h];

                tailer.last = tailer.board[ny][nx];

                swap(tailer.board[ny][nx],tailer.board[ny - dy[f1]][nx - dx[f1]]);

                tailer.step++;

                q[t] = tailer;

            }

        }

        h++;

    }

}

int main(){

    char cmd;

    int r1,r2,ans;

    for(r1 = ;r1 <= ;r1++){

        for(r2 = ;r2 <= ;r2++){

            cin>>cmd;

            if(cmd == 'O') first.board[r1][r2] = ;

            if(cmd == 'B') first.board[r1][r2] = ;

            if(cmd == 'W') first.board[r1][r2] = ;

        }

    }

    first.step = ;

    first.last = ;

    q[] = first;

    ans = bfs();

    cout<<ans;

    return ;

}

巴特西

codevs1004 四子连棋

最新文章

热门文章