Xtreme 10.0 - Checkers Challenge

这是 meelo 原创的 IEEEXtreme极限编程大赛题解

Xtreme 10.0 - Checkers Challenge
题目来源 第10届IEEE极限编程大赛
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/draughts-1

Watch the following YouTube video clip. Your task is to compute the number of possible ways the white player can win from an opening state of a single white piece in a game of Turkish Draughts. For more information on the game, you can view the Wikipedia page.
For this challenge, we will use the following variation on the official rules:
The black pieces can be arbitrary placed, and will not necessarily be located at places reachable in a legal game

1. A single white piece is a king if, and only if, it is placed in or reaches the top most line. Once a piece is a king it remains a king throughout.
2. A white piece can capture by jumping over a single black piece to the left, right or upwards, landing in the adjacent square
3. A white king can capture by jumping left, right, upwards or backwards and can skip arbitrary number of blank squares before and after the black piece
4. After capturing a black piece, the white piece (or king) must turn 90 degrees or keep moving in the same direction (no 180 degree turns are allowed).
5. We ask for the number of different ways the white player can win a single move. White wins by capturing all black pieces.

Input Format

Each input begins with an integer t, on a line by itself, indicating how many testcases are present.
Each testcase will contain 8 lines with the state of the board. The board will have a single white piece o, some black pieces x, and empty places .. White's side of the board is at the bottom of the board. So if the white piece were to reach to top row of the board, it would become a king.
In between each testcase is a blank line.

Constraints

1 ≤ t ≤ 5
There will always be at least 1, and no more than 16, black pieces in each game.
The game board will always be 8x8 squares in size.

Output Format

For each testcase, output, on a line by itself, the number of possible ways the white can win, or 0
if he cannot.

Sample Input

3
.......o
.x.x.x..
xxxx.xx.
........
........
.x.xx..x
x.......
..x...x.

........
........
....o...
........
....x...
........
........
........

...o....
........
...x....
........
........
........
........

Sample Output

1205

Explanation

The first testcase is the state of the board in the 56th second of the YouTube video. There are 12 ways in which this game can be won. These ways are represented below:
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 2
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 3
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 4
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 5
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 6
down 7, left 3, up 6, left 2, down 4, right 4, up 4, left 3, down 4, left 3, up 4, right 5, down 6, left 5, up 5, right 7
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 2
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 3
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 4
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 5
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 6
down 7, left 3, up 6, right 2, down 4, left 4, up 4, right 3, down 4, left 5, up 4, right 3, down 6, left 3, up 5, right 7

There is no way for white to win the second testcase.
For the final testcase, white has a king, and white can capture the single black piece, and land on any of the five spaces below the piece.

题目解析
这题是一个搜索题，用深度优先搜索可以解决。
题目中的游戏规则比较复杂，一定要仔细阅读。最初没有注意到，普通白子不能向下走，浪费了很多时间。
使用回溯法可以避免保存状态。

程序
C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool legal(int x, int y) {
    return (x>=0) && (x<8) && (y>=0) && (y<8);
}

int countWin(char board[8][8], bool isKing, int wx, int wy, int lastDir, int numBlack) {
    int count = 0;
    
    // game over
    if(numBlack == 0) return 1;
    
    int dir[4][2] = { {0,1}, {0,-1}, {-1,0}, {1,0} };
    int bx, by; // black piece to the left, right or upwards
    int sx, sy; // landing square
    
    if(!isKing) {
        // cannot go downwards, possible directions: 0, 1, 2
        for(int d=0; d<3; d++) {
            
            bx = wx + dir[d][0];
            by = wy + dir[d][1];
            sx = wx + dir[d][0] * 2;
            sy = wy + dir[d][1] * 2;
            
            if(board[bx][by]=='x' && legal(sx, sy) && board[sx][sy]=='.') {
                if(sx == 0) isKing = true;
                board[bx][by] = '.';
                numBlack--;
                count += countWin(board, isKing, sx, sy, d, numBlack);
                // backtrack
                board[bx][by] = 'x';
                numBlack++;
            }
        }
    }
    else {
        for(int d=0; d<4; d++) {
            if((d==0 && lastDir==1) || (d==1 && lastDir==0) || 
            (d==2 && lastDir==3) || (d==3 && lastDir==2)) {
                continue;
            }
            bx = by = -1;
            // white king can go at least 1 step, at most 6 steps
            for(int skipBefore=1; skipBefore<=6; skipBefore++) {
                int tx = wx + dir[d][0] * skipBefore;
                int ty = wy + dir[d][1] * skipBefore;
                if(legal(tx, ty) && board[tx][ty]=='x') {
                    bx = tx;
                    by = ty;
                    break;
                }
            }
            //cout << bx << ' ' << by << endl;
            if(!legal(bx, by)) continue;
            for(int skipAfter=1; skipAfter<=6; skipAfter++) {
                int tx = bx + dir[d][0] * skipAfter;
                int ty = by + dir[d][1] * skipAfter;
                if(legal(tx, ty) && board[tx][ty]=='.') {
                    board[bx][by] = '.';
                    numBlack--;
                    int C = countWin(board, isKing, tx, ty, d, numBlack);
                    count += C;
                    // backtrack
                    board[bx][by] = 'x';
                    numBlack++;
                }
                else {
                    break;
                }
                
            }
        }
    }

    return count;
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T;
    cin >> T;
    for(int t=0; t<T; t++) {
        char board[8][8];
        for(int l=0; l<8; l++) {
            cin >> board[l];
        }
        
        // check whether is king or not
        bool isKing = false;
        for(int c=0; c<8; c++) {
            if(board[0][c] == 'o') isKing = true;
        }
        
        // locate white piece
        int wx, wy, numBlack = 0;
        for(int l=0; l<8; l++) {
            for(int c=0; c<8; c++) {
                if(board[l][c] == 'o') {
                    wx = l;
                    wy = c;
                    board[l][c] = '.';
                }
                else if(board[l][c] == 'x') {
                    numBlack++;
                }
            }
        }
        cout << countWin(board, isKing, wx, wy, -1, numBlack) << endl;
        getchar();
    }
    return 0;
}

博客中的文章均为 meelo 原创，请务必以链接形式注明 本文地址