這是 meelo 原創(chuàng)的 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.

題目解析
這題是一個搜索題逸雹，用深度優(yōu)先搜索可以解決云挟。
題目中的游戲規(guī)則比較復(fù)雜园欣，一定要仔細閱讀。最初沒有注意到日矫，普通白子不能向下走，浪費了很多時間盈魁。
使用回溯法可以避免保存狀態(tài)窃诉。

程序
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 原創(chuàng)敦冬，請務(wù)必以鏈接形式注明 本文地址