铺地砖实例红与黑数字输入—C++递归算法实现迷宫问题

问题描述

在本题中，您站在一个黑色瓷砖上，并且只能向相邻的黑色瓷砖移动。任务是计算从起始位置能够到达的黑色瓷砖的总数。具体实现中，瓷砖的颜色通过数字表示：

- 0 表示黑色瓷砖

- 1 表示红色瓷砖

- 2 表示黑色瓷砖，并且是起始位置。

输入要求

第一行输入两个整数 N 和 M，分别表示房间的行数和列数，均不超过 20。接下来的 N 行，每行有 M 个整数，表示每块瓷砖的颜色。

输出要求

输出一个整数，表示从起始位置出发能到达的黑色瓷砖的总数，包括初始位置的瓷砖。

示例输入

9 6
0 0 1 0 0 0
0 0 0 0 0 0
1 2 0 0 0 1
0 0 1 0 0 0
1 0 0 1 0 0
0 0 0 0 0 1

示例输出

45

解题思路

本题采用递归算法解决，可以通过深度优先搜索（DFS）方法遍历所有相邻的黑色瓷砖，并记录已经访问过的瓷砖。以下是代码实现思路：

#include 
#include 
using namespace std;

int n, m;
vector> grid;
vector> visited;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(int x, int y) {
    visited[x][y] = true;
    for (int i = 0; i < 4 xss=removed xss=removed>= 0 && nx < n>= 0 && ny < m xss=removed xss=removed>> n >> m;
    grid.resize(n, vector(m));
    visited.resize(n, vector(m, false));
    int startX = -1, startY = -1;

    // 输入瓷砖数据
    for (int i = 0; i < n xss=removed>> grid[i][j];
            if (grid[i][j] == 2) {
                startX = i;
                startY = j;
            }
        }
    }

    // 从起始位置进行DFS遍历
    dfs(startX, startY);

    // 统计已访问的黑色瓷砖数量
    int result = 0;
    for (int i = 0; i < n xss=removed xss=removed xss=removed>

总结

通过递归方法遍历迷宫，每次遇到一个可到达的黑色瓷砖，递归搜索相邻的黑色瓷砖，直到无法再继续。最终输出可以到达的瓷砖数，确保正确性。

难点解析

• 通过递归实现深度优先搜索（DFS），遍历相邻的黑色瓷砖。
• 需要判断边界条件和避免重复访问。
• 递归搜索时要考虑相邻四个方向的瓷砖。