洛谷刷题日记||基础篇8

#include <iostream>
#include <vector>
using namespace std;

int N, M; // N为行数，M为列数
vector<vector<char>> field; // 表示田地的网格，每个元素是'W'或'.'
vector<vector<bool>> visited; // 用来记录网格是否访问过，防止重复计算

// 定义8个方向的偏移量，用于DFS时遍历相邻格子
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 行方向的变化量
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 列方向的变化量

// 深度优先搜索函数，用于从一个起点探索整个水坑
void dfs(int x, int y) {
    // 标记当前位置为已访问
    visited[x][y] = true;
    // 遍历8个相邻方向
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i]; // 计算新位置的行号
        int ny = y + dy[i]; // 计算新位置的列号
        // 判断新位置是否有效：在边界内，未被访问过，且是水格子
        if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && field[nx][ny] == 'W') {
            dfs(nx, ny); // 递归访问新位置
        }
    }
}

int main() {
    cin >> N >> M; // 读取网格的行数和列数
    field.resize(N, vector<char>(M)); // 初始化网格
    visited.resize(N, vector<bool>(M, false)); // 初始化访问标记数组为false
    
    // 输入田地网格数据
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> field[i][j]; // 读取每个格子的值（'W' 或 '.'）
        }
    }
    
    int pondCount = 0; // 统计水坑的数量
    // 遍历田地中的每个格子
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // 如果当前格子是水，且未被访问过，则启动一次DFS
            if (!visited[i][j] && field[i][j] == 'W') {
                dfs(i, j); // 使用DFS探索整个连通水坑
                pondCount++; // 每次启动DFS，说明发现了一个新的水坑
            }
        }
    }
    
    // 输出水坑的数量
    cout << pondCount << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 定义方向数组 directions，共 8 个方向
// 分别是：右、下、左、上、右下、左下、右上、左上
const int directions[8][2] = {
    {0, 1}, {1, 0}, {0, -1}, {-1, 0}, // 水平和垂直方向
    {1, 1}, {1, -1}, {-1, 1}, {-1, -1} // 对角线方向
};

// 检查坐标 (x, y) 是否在矩阵范围内
// x 和 y 都必须在 [0, n) 范围内才是有效位置
bool isValid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

// 在从 (x, y) 开始、沿 (dx, dy) 方向，寻找是否存在目标单词 word
// 如果找到完整的单词，将路径标记在 visited 矩阵中
bool findWord(vector<string>& matrix, vector<vector<bool>>& visited, int x, int y, int dx, int dy, const string& word) {
    int n = matrix.size(); // 获取矩阵的大小
    // 遍历目标单词的每个字符
    for (int i = 0; i < word.size(); i++) {
        int nx = x + i * dx; // 根据方向计算目标字符的行坐标
        int ny = y + i * dy; // 根据方向计算目标字符的列坐标
        // 检查是否越界或字符不匹配
        if (!isValid(nx, ny, n) || matrix[nx][ny] != word[i]) {
            return false; // 如果任意一个字符不符合，返回 false
        }
    }
    // 如果找到完整的单词，将路径标记为 true
    for (int i = 0; i < word.size(); i++) {
        int nx = x + i * dx; // 计算路径上的行坐标
        int ny = y + i * dy; // 计算路径上的列坐标
        visited[nx][ny] = true; // 标记该位置属于目标单词路径
    }
    return true; // 返回 true 表示找到了单词
}

int main() {
    int n;
    cin >> n; // 输入矩阵的大小 n
    vector<string> matrix(n); // 定义 n 行字符串组成的矩阵
    for (int i = 0; i < n; i++) {
        cin >> matrix[i]; // 输入矩阵的每一行
    }

    string target = "yizhong"; // 目标单词
    int targetLen = target.length(); // 目标单词的长度
    vector<vector<bool>> visited(n, vector<bool>(n, false)); // 定义标记矩阵，初始化为 false

    // 遍历矩阵中的每个位置，检查是否能找到 "yizhong"
    for (int i = 0; i < n; i++) { // 遍历每一行
        for (int j = 0; j < n; j++) { // 遍历每一列
            if (matrix[i][j] == 'y') { // 只有起点是 'y' 时，才有可能找到单词
                for (auto dir : directions) { // 遍历 8 个方向
                    findWord(matrix, visited, i, j, dir[0], dir[1], target);
                }
            }
        }
    }

    // 构造输出矩阵，根据 visited 矩阵决定输出内容
    for (int i = 0; i < n; i++) { // 遍历每一行
        for (int j = 0; j < n; j++) { // 遍历每一列
            if (!visited[i][j]) { // 如果该位置不在单词路径中
                cout << '*'; // 输出 '*'
            } else { // 如果该位置是单词路径的一部分
                cout << matrix[i][j]; // 输出原字符
            }
        }
        cout << endl; // 输出换行符，切换到下一行
    }

    return 0; // 程序结束，返回 0
}

这段代码的作用是从矩阵中的某个起点 (x, y) 开始，沿指定方向 (dx, dy) 检查能否连续找到目标单词 word。我们逐个字符进行匹配，并确保目标位置有效且字符符合要求。如果任一条件不满足，立即返回 false。下面是对每一部分的详细解释：

 for (int i = 0; i < word.size(); i++) {
        int nx = x + i * dx; // 根据方向计算目标字符的行坐标
        int ny = y + i * dy; // 根据方向计算目标字符的列坐标
        // 检查是否越界或字符不匹配
        if (!isValid(nx, ny, n) || matrix[nx][ny] != word[i]) {
            return false; // 如果任意一个字符不符合，返回 false
        }
    }

小技巧

1. 减少重复检查：由于 nx 和 ny 的计算是基于线性关系的，可以直接在循环中累计结果。
2. 提前终止：发现不匹配时立刻返回，节约时间。

这段代码的核心是通过数学计算实现精确的方向定位和单词匹配。

逐步解析

逆向思维

标记外部 0

1. 遍历矩阵边界的每一行和每一列。
   • 如果某个位置是 0 且未访问过，将其加入队列并标记为已访问。
2. 利用 BFS，检查所有与当前边界 0 连通的其他 0，标记它们为外部 0。

填充闭合圈内的 0

1. 遍历矩阵中的每个格子。
   • 如果某个位置是 0 且未被标记为外部 0（visited[i][j] == false），说明该格子在闭合圈内。
   • 将该格子的值修改为 2。

输出结果

• 遍历矩阵，逐个输出值，格式化输出。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 四个方向数组，用于表示上下左右移动的偏移量
const int directions[4][2] = {
    {0, 1},  // 右
    {1, 0},  // 下
    {0, -1}, // 左
    {-1, 0}  // 上
};

// 检查坐标 (x, y) 是否在矩阵范围内
bool isValid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

// 标记所有与矩阵边界连通的 0
void markOutsideZeroes(vector<vector<int>>& matrix, vector<vector<bool>>& visited) {
    int n = matrix.size();
    queue<pair<int, int>> q; // 队列用于 BFS 遍历

    // 遍历矩阵的四个边界，将边界上的 0 入队
    for (int i = 0; i < n; i++) {
        if (matrix[i][0] == 0 && !visited[i][0]) { // 左边界
            q.push({i, 0});       // 入队
            visited[i][0] = true; // 标记为已访问
        }
        if (matrix[i][n - 1] == 0 && !visited[i][n - 1]) { // 右边界
            q.push({i, n - 1});
            visited[i][n - 1] = true;
        }
    }
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0 && !visited[0][j]) { // 上边界
            q.push({0, j});
            visited[0][j] = true;
        }
        if (matrix[n - 1][j] == 0 && !visited[n - 1][j]) { // 下边界
            q.push({n - 1, j});
            visited[n - 1][j] = true;
        }
    }

    // 使用 BFS 遍历所有与边界连通的 0
    while (!q.empty()) {
        auto [x, y] = q.front(); // 取出队首元素
        q.pop();

        // 遍历当前点的上下左右四个方向
        for (auto dir : directions) {
            int nx = x + dir[0]; // 计算新坐标
            int ny = y + dir[1];
            // 如果新坐标有效且是未访问的 0，则将其入队
            if (isValid(nx, ny, n) && matrix[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true; // 标记为已访问
                q.push({nx, ny});       // 入队
            }
        }
    }
}

// 将闭合圈内的 0 填充为 2
void fillInnerZeroes(vector<vector<int>>& matrix, const vector<vector<bool>>& visited) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 如果当前格子是 0 且未被标记为外部 0
            if (matrix[i][j] == 0 && !visited[i][j]) {
                matrix[i][j] = 2; // 填充为 2
            }
        }
    }
}

int main() {
    int n;
    cin >> n; // 输入矩阵大小
    vector<vector<int>> matrix(n, vector<int>(n)); // 定义 n x n 的矩阵
    vector<vector<bool>> visited(n, vector<bool>(n, false)); // 标记矩阵，用于记录外部 0 是否已访问

    // 输入矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j]; // 逐个读取矩阵元素
        }
    }

    // 第一步：标记所有与边界连通的 0
    markOutsideZeroes(matrix, visited);

    // 第二步：将闭合圈内的 0 填充为 2
    fillInnerZeroes(matrix, visited);

    // 输出结果矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << matrix[i][j] << " "; // 输出矩阵元素
        }
        cout << endl; // 每行结束后换行
    }

    return 0;
}