首页 > 试题广场 >

下棋

[编程题]下棋
  • 热度指数:203 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
8x8的棋盘上,布有黑白两色棋子,白子先下,当白子下N手后,棋盘上最多有可能留下多少颗白子?

下法规则:
1.每次落子后,以该棋子为中心的8个方向(米字形的8条直线),如果有同色棋子,
且两个同色棋子之间连续排列着若干个异色棋子,无空白及同色棋子。则,这次落子可以把这些夹在中间的异色棋子全部翻色(即黑变白,白变黑)。

2. 黑白子交错落子。

3. 如果一个位置上有棋子,不能继续在该位置上落子;

4. 如果一个位置上落子后,不能翻对手的棋子,则该位置不能落子;

1表示黑色,2表示白色,0表示空白未落子
白棋落子后,棋盘变化情况如下所示:
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0    =>   0 0 0 1 2 0 0 0 
0 0 0 2 1 0 0 0         0 0 0 2 2 2 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0    =>   0 0 0 1 2 0 0 0 
0 0 1 2 1 2 0 0         0 0 1 2 1 1 1 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 


输入描述:
第一行为白子需要走的步数

接下来8行数据,指明棋盘上的棋子状态,其中1为黑子,2为白子,0为空位置


输出描述:
白子下完N手后,棋盘上的白子个数的最大可能。
示例1

输入

1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0
0 0 0 2 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

输出

4
这种逻辑题做起来还有点意思,这题目有两个坑要说一下,一是边界的棋子无法反转,二是初始棋盘不一定是最终状态。因为写的时候不知道输入样例还有第二个坑,只过了90%,最后一个样例就是考察对初始棋盘的处理,懒得改了。

import sys

hands = int(sys.stdin.readline().strip())

board = [list(map(int, sys.stdin.readline().strip().split()))
         for _ in range(8)]

res = 0
for row in range(8):
    for col in range(8):
        if board[row][col] == 2:
            res += 1

directions = [[-1, 1], [0, 1], [1, 1], [1, 0],
              [1, -1], [0, -1], [-1, -1], [-1, 0]]  # 八个方向基向量


def flip(board, coords):
    '''
    翻转棋盘
    :param board:
    :param coords: 需要翻转的棋子坐标
    :return: 翻转的棋子数量
    '''
    for row, col in coords:
        board[row][col] = board[row][col] % 2 + 1
    return len(coords)


def valid(board, row, col, color):
    '''
    检查当前坐标落子的有效性
    :param board: 棋盘
    :param row,col: 落子坐标
    :param color: 落子颜色
    :return: 可以被翻转棋子的坐标列表
    '''
    res = list()

    if board[row][col] != 0:  # 已存在棋子
        return res

    for dx, dy in directions:
        single_line_res = list()  # 单方向扫描到的异色棋子
        for t in range(1, 9):  # 基向量的倍率
            s_row, s_col = row + t * dx, col + t * dy

            # 该方向走到边界或遇到空
            if s_row < 0&nbs***bsp;s_row > 7 \
                   &nbs***bsp;s_col < 0&nbs***bsp;s_col > 7 \
                   &nbs***bsp;board[s_row][s_col] == 0:
                break
            # 遇到同色棋子
            elif board[s_row][s_col] == color:
                res.extend(single_line_res)
                single_line_res = list()  # 清空
                break
            # 异色棋子
            else:
                single_line_res.append([s_row, s_col])

    return res


def dfs(step, cur_res, color, board):
    global res, hands
    res = max(cur_res, res)

    if step == hands and color == 1:
        return

    for row in range(8):
        for col in range(8):
            coords = valid(board, row, col, color)
            if coords:
                board[row][col] = color  # 落子
                cur_res_bak = cur_res  # 备份用于状态还原

                if color == 2:
                    cur_res += 1
                    cur_res += flip(board, coords)
                else:
                    cur_res -= flip(board, coords)

                next_step = step + color % 2
                next_color = color % 2 + 1
                dfs(next_step, cur_res, next_color, board)

                # 状态还原
                board[row][col] = 0
                flip(board, coords)
                cur_res = cur_res_bak

    return


dfs(1, res, 2, board)
print(res)




发表于 2020-06-06 16:02:59 回复(0)
8×8的棋盘,题目的背景还是比较符合生活的。直接用回溯法穷举所有的可能性,模拟整个下棋的过程,在白子的剩余步数为0时更新棋盘上的最大白子数就可以了。思路很简单,但是debug的时候还挺麻烦的,需要耐心调试。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    static int maxCount = 0;
    static int[] dx = {1, -1, 0, 0, 1, -1, 1, -1};
    static int[] dy = {1, -1, 1, -1, 0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] grid = new int[8][8];
        int count = 0;      // 初始白子数
        for(int i = 0; i < 8; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < 8; j++){
                grid[i][j] = Integer.parseInt(line[j]);
                if(grid[i][j] == 2) {
                    count++;
                }
            }
        }
        dfs(grid, n, 2, count);
        System.out.println(maxCount);
    }
    
    private static void dfs(int[][] grid, int rest, int color, int count){
        if(rest == 0) {
            // 没有剩余步数了就更新白子数
            maxCount = Math.max(maxCount, count);
            return;
        }
        // 尝试落子到各个位置
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++){
                if(grid[i][j] != 0) {
                    continue;
                }
                grid[i][j] = color;    // 落子
                // 如果在该位置落子,有哪些位置的棋子可以反转
                LinkedList<int[]> flipPos = getPosForFlip(grid, i, j, color);
                if(!flipPos.isEmpty()){
                    flip(grid, flipPos);
                    if(color == 2){  // 如果当前为白子,flipPos的长度为翻转新增的白子数
                        // 这一步下的白子,剩余步数减1,下一步下黑子
                        dfs(grid, rest - 1, 1, count + 1 + flipPos.size());
                    }else{  // 如果当前为黑子,flipPos的长度为翻转减少的白子数
                        // 这一步下的黑子,剩余步数不减少,下一步下白子
                        dfs(grid, rest, 2, count - flipPos.size());
                    }
                }
                // 回溯
                grid[i][j] = 0;
                flip(grid, flipPos);
            }
        }
    }
    
    private static LinkedList<int[]> getPosForFlip(int[][] grid, int i, int j, int color) {
        LinkedList<int[]> candicates = new LinkedList<>();
        for(int k = 0; k < 8; k++){    // 走的方向
            LinkedList<int[]> tempCandicates = new LinkedList<>();
            for(int step = 1; step <= 8; step++){    // 沿着这一方向走的步数
                int x = i + step * dx[k], y = j + step * dy[k];
                // 越界或不存在棋子
                if(x < 0 || x > 7 || y < 0 || y > 7 || grid[x][y] == 0)
                    break;
                if(grid[x][y] == color){
                    // 遇到同色棋子,才能把中间异色棋子的位置加入结果集
                    candicates.addAll(tempCandicates);
                    break;       // 一个方向不能无限制翻转下去
                }else{
                    // 遇到异色棋子,先收集位置
                    tempCandicates.add(new int[]{x, y});
                }
            }
        }
        return candicates;
    }
    
    private static void flip(int[][] grid, LinkedList<int[]> list){
        if(list.isEmpty()) return;
        Iterator<int[]> iterator = list.iterator();
        while(iterator.hasNext()){
            int[] pos = iterator.next();
            if(grid[pos[0]][pos[1]] == 1){
                grid[pos[0]][pos[1]] = 2;
            }else if(grid[pos[0]][pos[1]] == 2){
                grid[pos[0]][pos[1]] = 1;
            }
        }
    }
}

编辑于 2021-12-07 15:36:35 回复(0)

问题分析

棋盘很小(8*8),且玩家只能在合法的位置落子,因此推测游戏的状态数可能不多,于是尝试直接dfs枚举所有可能的情况。

代码实现

为了方便使用了全局变量,不过并不推荐这么做……

代码里出现的函数:

  • find:从当前位置和方向出发,查找第一个颜色等于clr的棋子
  • set:从当前位置和方向出发,把前cnt个棋子的颜色置为clr
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int ans;

int find(int board[][8], int i, int j, int di, int dj, int clr, int rev) {
    i += di;
    j += dj;
    int cnt = 1;
    while(0 <= i && i < 8 && 0 <= j && j < 8) {
        if(board[i][j] == clr) {
            return cnt;
        }
        else if(board[i][j] != rev) {
            return 0;
        }
        i += di;
        j += dj;
        cnt++;
    }
    return 0;
}
void set(int board[][8], int i, int j, int di, int dj, int cnt, int clr) {
    for(int x = 0; x < cnt; x++) {
        board[i][j] = clr;
        i += di;
        j += dj;
    }
}
void dfs(int cnt_step, int board[][8]) {
    if(cnt_step == n) {
        int cur = 0;
        for(int i = 0; i < 8; i++) {
            for(int j = 0; j < 8; j++) {
                if(board[i][j] == 2) {
                    cur++;
                }
            }
        }
        ans = max(ans, cur);
    }
    else {
        int clr = 2 - (cnt_step % 2);
        int rev = 3 - clr;
        int nxt_board[8][8];
        for(int i = 0; i < 8; i++) {
            for(int j = 0; j < 8; j++) {
                if(board[i][j] == 0) {
                    bool flag = false;
                    for(int di = -1; di <= 1; di++) {
                        for(int dj = -1; dj <= 1; dj++) {
                            if(di == 0 && dj == 0) {
                                continue;
                            }
                            int cnt = find(board, i, j, di, dj, clr, rev);
                            if(cnt > 1) {
                                if(!flag) {
                                    memcpy(nxt_board, board, sizeof(int) * 64);
                                    flag = true;
                                }
                                set(nxt_board, i, j, di, dj, cnt, clr);
                            }
                        }
                    }
                    if(flag) {
                        dfs(cnt_step + 1, nxt_board);
                    }
                }
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    n = 2 * n - 1;
    int board[8][8];
    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            scanf("%d", &board[i][j]);
        }
    }
    ans = 0;
    dfs(0, board);
    printf("%d\n", ans);
    return 0;
}
发表于 2019-08-21 01:21:22 回复(3)