P3956 棋盘

May 10, 2026 · 11 分钟阅读 · 深度优先搜索 ·

文章目录

题目信息

字段	内容
题号	P3956
难度	普及+
知识点	深度优先搜索、记忆化搜索

题目描述

有一个 m × m 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。

你需要从棋盘的最左上角走到棋盘的最右下角。

行走规则：

任何一个时刻，你所站在的位置必须是有颜色的（不能是无颜色）
假设当前所在格子颜色为 A，目标格子颜色为 B：
- 如果 A = B（同色）：不需要花费金币
- 如果 A ≠ B（异色）：需要花费 1 个金币
- 如果 B 是无颜色：可以使用魔法，花费 2 个金币将 B 染成 A 的颜色

数据范围：

1 ≤ m ≤ 100
最多有 n 个有色格子（0 ≤ n ≤ 20m）

输入格式

第一行两个正整数 m 和 n
接下来 n 行，每行三个整数 x、y、c：
- (x, y) 表示格子的坐标
- c = 1 表示红色，c = 0 表示黄色

输出格式

输出一个整数，表示最少花费的金币数量
如果无法到达，输出 -1

样例

输入 #1：

输出 #1：

-1

输入 #2：

输出 #2：

解题思路

核心思想

这道题是典型的 DFS + 记忆化搜索（或 BFS + 优先队列）。

为什么需要记忆化？

从 (1,1) 到 (x,y) 的最小花费是固定的。如果我们之前已经找到了一个到达 (x,y) 的花费，之后又走到 (x,y) 且花费更大，就没有必要继续搜索了。

状态设计

dfs(x, y, color) 表示从 (1,1) 走到 (x,y)，且当前格子颜色为 color 的最小花费。

但代码中使用了另一种方法：直接记录到达每个格子的最小花费。

算法流程

初始化：dist[x][y] = INF（表示还未到达）
从 (1,1) 开始 DFS：
- 尝试向 4 个方向走
- 计算走到新格子的花费
- 如果新花费 < dist[new_x][new_y]，则更新并继续搜索
输出结果：dist[m][m]

算法核心

本题使用 DFS + 记忆化搜索。

关键设计：z 参数标记当前状态

z = -1：还在起点，还没有确定颜色
z != -1：当前格子颜色是 z

染色规则：

只能在起点染色：当 z == -1 且目标格子无颜色时，花费 2 染色
上路后不能染色：当 z != -1 且目标格子无颜色时，continue 跳过

这个规则是本题的核心，已通过所有测试点 ✅

完整代码

C++

#include <bits/stdc++.h>

namespace {

// 棋盘最大尺寸（题目中 m ≤ 100）
constexpr int kMaxBoardSize = 100;
// 距离数组的初始值（表示不可达）
constexpr int kUnreachable = 20000;

// 棋盘颜色：-1 表示无颜色，0 表示黄色，1 表示红色
int board[kMaxBoardSize + 1][kMaxBoardSize + 1];
// dist[x][y] = 到达 (x, y) 的最小花费
int dist[kMaxBoardSize + 1][kMaxBoardSize + 1];
// visited[x][y] = 是否在当前搜索路径上访问过 (x, y)
int visited[kMaxBoardSize + 1][kMaxBoardSize + 1];

// 四个方向的偏移量：下、右、上、左
int dir_x[5] = {0, 1, -1, 0, 0};
int dir_y[5] = {0, 0, 0, 1, -1};

// 全局变量：棋盘大小
int board_size;
int colored_cells_count;

/**
 * DFS + 记忆化搜索
 * @param x 当前行坐标（1-based）
 * @param y 当前列坐标（1-based）
 * @param current_color 当前格子的颜色（-1 表示还在起点，0 或 1 表示已确定颜色）
 */
void DfsSearch(int x, int y, int current_color) {
    if (x < 1 || y < 1 || x > board_size || y > board_size) {
        return;
    }

    for (int i = 1; i <= 4; ++i) {
        int next_x = x + dir_x[i];
        int next_y = y + dir_y[i];

        // 越界或已在当前路径上访问过
        if (next_x < 1 || next_y < 1 || next_x > board_size || next_y > board_size) {
            continue;
        }
        if (visited[next_x][next_y] == 1) {
            continue;
        }

        int move_cost = 0;
        int next_color = -1;

        if (current_color != -1) {
            // 已经在路上，当前已有颜色
            if (board[next_x][next_y] != -1) {
                // 目标格子有颜色
                move_cost = (current_color != board[next_x][next_y]) ? 1 : 0;
            } else {
                // 目标格子无颜色，不能染色，跳过
                continue;
            }
        } else {
            // 还在起点
            if (board[next_x][next_y] == -1) {
                // 目标格子也无颜色，花费 2 染色
                move_cost = 2;
                next_color = board[x][y];
            } else {
                // 目标格子有颜色
                move_cost = (board[x][y] != board[next_x][next_y]) ? 1 : 0;
            }
        }

        // 记忆化：如果找到更小的花费，则更新并继续搜索
        if (dist[next_x][next_y] > dist[x][y] + move_cost) {
            dist[next_x][next_y] = dist[x][y] + move_cost;
            visited[x][y] = 1;
            DfsSearch(next_x, next_y, next_color);
            visited[x][y] = 0;
        }
    }
}

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> board_size >> colored_cells_count;

    // 初始化距离数组
    for (int i = 0; i <= kMaxBoardSize; ++i) {
        for (int j = 0; j <= kMaxBoardSize; ++j) {
            dist[i][j] = kUnreachable;
        }
    }
    dist[1][1] = 0;

    // 初始化棋盘（全部无颜色）
    for (int i = 1; i <= board_size; ++i) {
        for (int j = 1; j <= board_size; ++j) {
            board[i][j] = -1;
        }
    }

    // 读入有色格子
    for (int i = 1; i <= colored_cells_count; ++i) {
        int pos_x, pos_y, color;
        std::cin >> pos_x >> pos_y >> color;
        board[pos_x][pos_y] = color;
    }

    visited[1][1] = 1;
    DfsSearch(1, 1, -1);

    if (dist[board_size][board_size] == kUnreachable) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << dist[board_size][board_size] << std::endl;
    }

    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

// 常量定义
const (
	maxBoardSize = 100  // 棋盘最大尺寸
	unreachable  = 20000 // 不可达标记
)

// 棋盘颜色：-1 表示无颜色，0 表示黄色，1 表示红色
var board [maxBoardSize + 1][maxBoardSize + 1]int
var dist [maxBoardSize + 1][maxBoardSize + 1]int
var visited [maxBoardSize + 1][maxBoardSize + 1]bool

// 四个方向的偏移量：下、右、上、左
var dirX = [5]int{0, 1, -1, 0, 0}
var dirY = [5]int{0, 0, 0, 1, -1}

var boardSize int
var coloredCellsCount int

// DfsSearch DFS + 记忆化搜索
// x, y: 当前坐标（1-based）
// currentColor: 当前格子颜色（-1 表示还在起点，0 或 1 表示已确定颜色）
func DfsSearch(x, y, currentColor int) {
	if x < 1 || y < 1 || x > boardSize || y > boardSize {
		return
	}

	for i := 1; i <= 4; i++ {
		nextX := x + dirX[i]
		nextY := y + dirY[i]

		// 越界或已在当前路径上访问过
		if nextX < 1 || nextY < 1 || nextX > boardSize || nextY > boardSize {
			continue
		}
		if visited[nextX][nextY] {
			continue
		}

		moveCost := 0
		nextColor := -1

		if currentColor != -1 {
			// 已经在路上，当前已有颜色
			if board[nextX][nextY] != -1 {
				// 目标格子有颜色
				if currentColor != board[nextX][nextY] {
					moveCost = 1
				}
			} else {
				// 目标格子无颜色，不能染色，跳过
				continue
			}
		} else {
			// 还在起点
			if board[nextX][nextY] == -1 {
				// 目标格子也无颜色，花费 2 染色
				moveCost = 2
				nextColor = board[x][y]
			} else {
				// 目标格子有颜色
				if board[x][y] != board[nextX][nextY] {
					moveCost = 1
				}
			}
		}

		// 记忆化：如果找到更小的花费，则更新并继续搜索
		if dist[nextX][nextY] > dist[x][y]+moveCost {
			dist[nextX][nextY] = dist[x][y] + moveCost
			visited[x][y] = true
			DfsSearch(nextX, nextY, nextColor)
			visited[x][y] = false
		}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	fmt.Fscan(in, &boardSize, &coloredCellsCount)

	// 初始化距离数组
	for i := 0; i <= maxBoardSize; i++ {
		for j := 0; j <= maxBoardSize; j++ {
			dist[i][j] = unreachable
		}
	}
	dist[1][1] = 0

	// 初始化棋盘（全部无颜色）
	for i := 1; i <= boardSize; i++ {
		for j := 1; j <= boardSize; j++ {
			board[i][j] = -1
		}
	}

	// 读入有色格子
	for i := 1; i <= coloredCellsCount; i++ {
		var posX, posY, color int
		fmt.Fscan(in, &posX, &posY, &color)
		board[posX][posY] = color
	}

	visited[1][1] = true
	DfsSearch(1, 1, -1)

	if dist[boardSize][boardSize] == unreachable {
		fmt.Println(-1)
	} else {
		fmt.Println(dist[boardSize][boardSize])
	}
}

Java

import java.io.*;
import java.util.*;

public class Main {
    // 常量定义
    private static final int MAX_BOARD_SIZE = 100;  // 棋盘最大尺寸
    private static final int UNREACHABLE = 20000;    // 不可达标记

    // 棋盘颜色：-1 表示无颜色，0 表示黄色，1 表示红色
    private static int[][] board = new int[MAX_BOARD_SIZE + 1][MAX_BOARD_SIZE + 1];
    private static int[][] dist = new int[MAX_BOARD_SIZE + 1][MAX_BOARD_SIZE + 1];
    private static boolean[][] visited = new boolean[MAX_BOARD_SIZE + 1][MAX_BOARD_SIZE + 1];

    // 四个方向的偏移量：下、右、上、左
    private static final int[] dirX = {0, 1, -1, 0, 0};
    private static final int[] dirY = {0, 0, 0, 1, -1};

    private static int boardSize;
    private static int coloredCellsCount;

    /**
     * DFS + 记忆化搜索
     * @param x 当前行坐标（1-based）
     * @param y 当前列坐标（1-based）
     * @param currentColor 当前格子颜色（-1 表示还在起点，0 或 1 表示已确定颜色）
     */
    private static void dfsSearch(int x, int y, int currentColor) {
        for (int i = 1; i <= 4; ++i) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];

            // 越界或已在当前路径上访问过
            if (nextX < 1 || nextY < 1 || nextX > boardSize || nextY > boardSize) {
                continue;
            }
            if (visited[nextX][nextY]) {
                continue;
            }

            int moveCost = 0;
            int nextColor = -1;

            if (currentColor != -1) {
                // 已经在路上，当前已有颜色
                if (board[nextX][nextY] != -1) {
                    // 目标格子有颜色
                    if (currentColor != board[nextX][nextY]) {
                        moveCost = 1;
                    }
                } else {
                    // 目标格子无颜色，不能染色，跳过
                    continue;
                }
            } else {
                // 还在起点
                if (board[nextX][nextY] == -1) {
                    // 目标格子也无颜色，花费 2 染色
                    moveCost = 2;
                    nextColor = board[x][y];
                } else {
                    // 目标格子有颜色
                    if (board[x][y] != board[nextX][nextY]) {
                        moveCost = 1;
                    }
                }
            }

            // 记忆化：如果找到更小的花费，则更新并继续搜索
            if (dist[nextX][nextY] > dist[x][y] + moveCost) {
                dist[nextX][nextY] = dist[x][y] + moveCost;
                visited[x][y] = true;
                dfsSearch(nextX, nextY, nextColor);
                visited[x][y] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner fs = new FastScanner(System.in);
        boardSize = fs.nextInt();
        coloredCellsCount = fs.nextInt();

        // 初始化距离数组
        for (int i = 0; i <= MAX_BOARD_SIZE; ++i) {
            for (int j = 0; j <= MAX_BOARD_SIZE; ++j) {
                dist[i][j] = UNREACHABLE;
            }
        }
        dist[1][1] = 0;

        // 初始化棋盘（全部无颜色）
        for (int i = 1; i <= boardSize; ++i) {
            for (int j = 1; j <= boardSize; ++j) {
                board[i][j] = -1;
            }
        }

        // 读入有色格子
        for (int i = 1; i <= coloredCellsCount; ++i) {
            int posX = fs.nextInt();
            int posY = fs.nextInt();
            int color = fs.nextInt();
            board[posX][posY] = color;
        }

        visited[1][1] = true;
        dfsSearch(1, 1, -1);

        if (dist[boardSize][boardSize] == UNREACHABLE) {
            System.out.println(-1);
        } else {
            System.out.println(dist[boardSize][boardSize]);
        }
    }

    // 快速输入类
    private static class FastScanner {
        private final BufferedReader br;
        private StringTokenizer st;

        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreElements()) {
                String line = br.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}

Python

import sys
sys.setrecursionlimit(10000)

# 常量定义
MAX_BOARD_SIZE = 100  # 棋盘最大尺寸
UNREACHABLE = 20000   # 不可达标记

# 棋盘颜色：-1 表示无颜色，0 表示黄色，1 表示红色
board = [[-1] * (MAX_BOARD_SIZE + 1) for _ in range(MAX_BOARD_SIZE + 1)]
dist = [[UNREACHABLE] * (MAX_BOARD_SIZE + 1) for _ in range(MAX_BOARD_SIZE + 1)]
visited = [[False] * (MAX_BOARD_SIZE + 1) for _ in range(MAX_BOARD_SIZE + 1)]

# 四个方向的偏移量：下、右、上、左
DIR_X = [0, 1, -1, 0, 0]
DIR_Y = [0, 0, 0, 1, -1]

board_size = 0
colored_cells_count = 0


def dfs_search(x: int, y: int, current_color: int) -> None:
    """
    DFS + 记忆化搜索

    Args:
        x: 当前行坐标（1-based）
        y: 当前列坐标（1-based）
        current_color: 当前格子颜色（-1 表示还在起点，0 或 1 表示已确定颜色）
    """
    for i in range(1, 5):
        next_x = x + DIR_X[i]
        next_y = y + DIR_Y[i]

        # 越界或已在当前路径上访问过
        if next_x < 1 or next_y < 1 or next_x > board_size or next_y > board_size:
            continue
        if visited[next_x][next_y]:
            continue

        move_cost = 0
        next_color = -1

        if current_color != -1:
            # 已经在路上，当前已有颜色
            if board[next_x][next_y] != -1:
                # 目标格子有颜色
                if current_color != board[next_x][next_y]:
                    move_cost = 1
            else:
                # 目标格子无颜色，不能染色，跳过
                continue
        else:
            # 还在起点
            if board[next_x][next_y] == -1:
                # 目标格子也无颜色，花费 2 染色
                move_cost = 2
                next_color = board[x][y]
            else:
                # 目标格子有颜色
                if board[x][y] != board[next_x][next_y]:
                    move_cost = 1

        # 记忆化：如果找到更小的花费，则更新并继续搜索
        if dist[next_x][next_y] > dist[x][y] + move_cost:
            dist[next_x][next_y] = dist[x][y] + move_cost
            visited[x][y] = True
            dfs_search(next_x, next_y, next_color)
            visited[x][y] = False


def main() -> None:
    global board_size, colored_cells_count

    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    board_size = int(next(it))
    colored_cells_count = int(next(it))

    # 初始化距离数组
    for i in range(MAX_BOARD_SIZE + 1):
        for j in range(MAX_BOARD_SIZE + 1):
            dist[i][j] = UNREACHABLE
    dist[1][1] = 0

    # 初始化棋盘（全部无颜色）
    for i in range(1, board_size + 1):
        for j in range(1, board_size + 1):
            board[i][j] = -1

    # 读入有色格子
    for _ in range(colored_cells_count):
        pos_x = int(next(it))
        pos_y = int(next(it))
        color = int(next(it))
        board[pos_x][pos_y] = color

    visited[1][1] = True
    dfs_search(1, 1, -1)

    if dist[board_size][board_size] == UNREACHABLE:
        print(-1)
    else:
        print(dist[board_size][board_size])


if __name__ == "__main__":
    main()

JavaScript

// 常量定义
const MAX_BOARD_SIZE = 100;  // 棋盘最大尺寸
const UNREACHABLE = 20000;   // 不可达标记

// 棋盘颜色：-1 表示无颜色，0 表示黄色，1 表示红色
let board = Array.from({ length: MAX_BOARD_SIZE + 1 }, () =>
    Array(MAX_BOARD_SIZE + 1).fill(-1)
);
let dist = Array.from({ length: MAX_BOARD_SIZE + 1 }, () =>
    Array(MAX_BOARD_SIZE + 1).fill(UNREACHABLE)
);
let visited = Array.from({ length: MAX_BOARD_SIZE + 1 }, () =>
    Array(MAX_BOARD_SIZE + 1).fill(false)
);

// 四个方向的偏移量：下、右、上、左
const DIR_X = [0, 1, -1, 0, 0];
const DIR_Y = [0, 0, 0, 1, -1];

let boardSize = 0;
let coloredCellsCount = 0;

/**
 * DFS + 记忆化搜索
 * @param {number} x - 当前行坐标（1-based）
 * @param {number} y - 当前列坐标（1-based）
 * @param {number} currentColor - 当前格子颜色（-1 表示还在起点，0 或 1 表示已确定颜色）
 */
function dfsSearch(x, y, currentColor) {
    for (let i = 1; i <= 4; i++) {
        const nextX = x + DIR_X[i];
        const nextY = y + DIR_Y[i];

        // 越界或已在当前路径上访问过
        if (nextX < 1 || nextY < 1 || nextX > boardSize || nextY > boardSize) {
            continue;
        }
        if (visited[nextX][nextY]) {
            continue;
        }

        let moveCost = 0;
        let nextColor = -1;

        if (currentColor !== -1) {
            // 已经在路上，当前已有颜色
            if (board[nextX][nextY] !== -1) {
                // 目标格子有颜色
                if (currentColor !== board[nextX][nextY]) {
                    moveCost = 1;
                }
            } else {
                // 目标格子无颜色，不能染色，跳过
                continue;
            }
        } else {
            // 还在起点
            if (board[nextX][nextY] === -1) {
                // 目标格子也无颜色，花费 2 染色
                moveCost = 2;
                nextColor = board[x][y];
            } else {
                // 目标格子有颜色
                if (board[x][y] !== board[nextX][nextY]) {
                    moveCost = 1;
                }
            }
        }

        // 记忆化：如果找到更小的花费，则更新并继续搜索
        if (dist[nextX][nextY] > dist[x][y] + moveCost) {
            dist[nextX][nextY] = dist[x][y] + moveCost;
            visited[x][y] = true;
            dfsSearch(nextX, nextY, nextColor);
            visited[x][y] = false;
        }
    }
}

/**
 * 主函数
 */
function main() {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\s+/);
    const it = input[Symbol.iterator]();

    boardSize = parseInt(it.next().value);
    coloredCellsCount = parseInt(it.next().value);

    // 初始化距离数组
    for (let i = 0; i <= MAX_BOARD_SIZE; i++) {
        for (let j = 0; j <= MAX_BOARD_SIZE; j++) {
            dist[i][j] = UNREACHABLE;
        }
    }
    dist[1][1] = 0;

    // 初始化棋盘（全部无颜色）
    for (let i = 1; i <= boardSize; i++) {
        for (let j = 1; j <= boardSize; j++) {
            board[i][j] = -1;
        }
    }

    // 读入有色格子
    for (let i = 0; i < coloredCellsCount; i++) {
        const posX = parseInt(it.next().value);
        const posY = parseInt(it.next().value);
        const color = parseInt(it.next().value);
        board[posX][posY] = color;
    }

    visited[1][1] = true;
    dfsSearch(1, 1, -1);

    if (dist[boardSize][boardSize] === UNREACHABLE) {
        console.log(-1);
    } else {
        console.log(dist[boardSize][boardSize]);
    }
}

main();

关键代码讲解

1. 常量定义

constexpr int kMaxBoardSize = 100;   // 棋盘最大尺寸
constexpr int kUnreachable = 20000;  // 不可达标记

使用 constexpr 定义常量，k 前缀符合 Google 常量命名规范。

2. `current_color` 参数的含义

void DfsSearch(int x, int y, int current_color)

current_color = -1：当前还在起点，还没有确定颜色
current_color != -1：当前格子颜色是 0 或 1

3. 花费计算逻辑

if (current_color != -1) {
    // 已经在路上，当前已有颜色
    if (board[next_x][next_y] != -1) {
        move_cost = (current_color != board[next_x][next_y]) ? 1 : 0;
    } else {
        continue;  // 目标格子无颜色，不能染色
    }
} else {
    // 还在起点
    if (board[next_x][next_y] == -1) {
        move_cost = 2;  // 花费 2 染色
        next_color = board[x][y];
    } else {
        move_cost = (board[x][y] != board[next_x][next_y]) ? 1 : 0;
    }
}

关键点：只有 current_color == -1（还在起点）时才能染色。

4. 记忆化数组 `dist[][]`

if (dist[next_x][next_y] > dist[x][y] + move_cost) {
    dist[next_x][next_y] = dist[x][y] + move_cost;
    // 继续搜索...
}

这是记忆化搜索的核心：dist[x][y] 记录到达 (x,y) 的最小花费。如果新的花费更大，就剪枝。

复杂度分析

方法	时间复杂度	空间复杂度
DFS + 记忆化	O(m²)	O(m²)

解释：

每个格子只会被更新有限次（每次更新都是找到更小的花费）
棋盘大小为 m × m，最多 10000 个格子
实际运行很快

易错点

起点处理：起点 (1,1) 可能是无颜色的，需要先染色
无色格子处理：只能在起点染色，上路后遇到无颜色格子要 continue 跳过
记忆化条件：是 dist[next_x][next_y] > dist[x][y] + move_cost，不是 >=
数组初始化：距离数组要初始化为 kUnreachable（表示不可达）
坐标越界：检查 next_x < 1 || next_y < 1 || next_x > board_size || next_y > board_size