下棋

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)

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;
            }
        }
    }
}