ACM-Alice and Bob

题目描述：Alice and Bob

One day, Alice asks Bob to play a game called “K-in-a-row”. There is a game board whose size is N*M. Alice plays first, and they alternate in placing a piece of their color on an empty intersection. The winner is the first player to get an unbroken row of K stones horizontally, vertically, or diagonally. Now given the last situation of the game board, I would like to know who win or just a draw?

输入

The first line of input is the number of test cases T.

For each test case. The first line contains three integers N(3<= N <=15), M(3<=M<=15) and K(3<=K<=6).The next N line, each line contains M pieces, ‘A’ means Alice’s place and ‘B’ means Bob’s place while ‘O’ means empty. It is promised that at most one player wins.

输出

For each test case output the answer on a single line, if Alice wins then print “Alice Win!”, if Bob wins then print ”Bob Win!”, if no one wins, then print ”No Win!”.

样例输入

2

6 6 6

AOOOOO

BABBOO

OOAOBO

OOOAOO

OOBOAO

OOOOOA

5 5 3

AOBOA

BABAO

OOBOO

OOOOO

OOOOO

样例输出

Alice Win!

Bob Win!

思路：就是个五子棋，DFS即可。但是我的代码没有A，找不到问题。所以附上我的代码和正确代码。

我的代码：

// Alice and Bob_K_win.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

//备注：没有AC！

#include <iostream>

#include <cstring>

using namespace std;

const int MAX = ;

int t, n, m, k,ans, vis[MAX][MAX],dir[][] = { , , -, , , , , -, , , -, -, , -, -,  };

char map[MAX][MAX];

void DFS(int x, int y,int a,int b)

{

    //cout << "x:" << x << "\ty:" << y << "\ta:" << a << "\tb:" << b << endl;

    if (ans != ) return;

    if (a == k || b == k)

    {

        if (a == k) ans = ;

        else ans = ;

        return;

    }

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

    {

        int nx = x + dir[i][];

        int ny = y + dir[i][];

        if (nx >=  && nx < n && ny >=  && ny < m && !vis[nx][ny] && map[nx][ny] != 'O')

        {

            //cout << "nx:" << nx << "\tny:" << ny << "\tmap[nx][ny]:" << map[nx][ny] << endl;

            vis[nx][ny] = ;

            if (map[nx][ny] == 'A') DFS(nx, ny, a + , b);

            else DFS(nx, ny, a, b + );

        }

    }

}

int main()

{

    cin >> t;

    while (t--)

    {

        memset(vis, , sizeof(vis));

        memset(map, '\0', sizeof(map));

        ans = ;

        cin >> n >> m >> k;

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

            cin >> map[i];

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

        {

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

            {

                if (map[i][j] != 'O' && !vis[i][j])

                {

                    vis[i][j] = ;

                    if (map[i][j] == 'A') DFS(i, j, , );

                    else if (map[i][j] == 'B') DFS(i, j, , );

                }

            }

        }

        if (ans == )

            cout << "Alice Win!" << endl;

        else if (ans == )

            cout << "Bob Win!" << endl;

        else

            cout << "No Win!" << endl;

    }

}

正确的代码：

#include<cstdio>

#include<iostream>

using namespace std;

int n,m,k,flag;

char map[][];

void dfs(int x,int y,int num,int dis,char e)

{

    if(num>k)

    {

        flag=;

        if(e=='A')

            cout<<"Alice Win!"<<endl;

        else

            cout<<"Bob Win!"<<endl;

        return ;

    }

    if(map[x][y]==e && x<n && x>= && y<m && y>=)

    {

        switch(dis)

        {

        case : dfs(x,y+,num+,dis,e);break;

        case : dfs(x,y-,num+,dis,e);break;

        case : dfs(x+,y,num+,dis,e);break;

        case : dfs(x-,y,num+,dis,e);break;

        case : dfs(x+,y+,num+,dis,e);break;

        case : dfs(x+,y-,num+,dis,e);break;

        case : dfs(x-,y-,num+,dis,e);break;

        case : dfs(x-,y+,num+,dis,e);break;

        }

    }

}

void solve()

{

    flag=;

    for(int i=;i<n;i++)//A

    {

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

        {

            if(map[i][j]=='A')

            {

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

                    dfs(i,j,,k,'A');

            }

            if(flag)

                break;

        }

        if(flag)

            break;

    }

    if(!flag)

    {

        for(int i=;i<n;i++)//B

        {

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

            {

                if(map[i][j]=='B')

                {

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

                        dfs(i,j,,k,'B');

                }

                if(flag)

                    break;

            }

            if(flag)

                break;

        }

    }

    if(!flag)

        cout<<"No Win!"<<endl;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n>>m>>k;

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

        {

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

                cin>>map[i][j];

        }

        solve();

    }

    return ;

}

巴特西

ACM-Alice and Bob

输入

输出

样例输入

样例输出

最新文章

热门文章