一、題目

參考鏈接：https://sars2025.blog.csdn.net/article/details/141748083

題目描述

現有一個機器人口，可放置于MxN的網格中任意位置，每個網格包含一個整數編號，當相鄰網格的數字編號差值的絕對值小于等
于1時，機器人可以在網格間移動。
問題:求機器人可活動的最大范圍對應的網格點數目
說明:網格左上角坐標為(0，0)，右下角坐標為(m-1，n-1)，機器人只能在相鄰網格間上下左右移動

輸入輸出

輸入
第1行輸入為M和N，M示網格的行數N表示網格的列數
之后M行表示網格數值，每行N個數值(數值大小用k示)
數值間用單個空格分隔，行首行尾無多余空格。
M、N、k均為整數，且1≤M，N≤150，0≤k≤50
輸出
輸出1行，包含1個數字，表示最大活動區域的網格點數目，行首行尾無多余空格

樣例1

輸入
4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

輸出
6

一、代碼與思路

🧠C++語言思路

1.首先定義一個深度優先搜索函數dfs，用于計算從指定位置出發的活動區域的網格點數目
2.在dfs函數中，首先獲取網格的行數m和列數n，并初始化活動區域的網格點數目為1。然后標記當前網格為已訪問狀態,
3.定義一個存儲上下左右四個方向偏移量的directions數組。
4.遍歷directions數組中的每個方向，計算新的坐標nx和ny。
5.如果新坐標滿足條件(在網格范圍內、未被訪問、相鄰網格編號差值的絕對值小于等于1)，則遞歸調用dfs函數計算新位置的活動區
域的網格點數目，并將其累加到area中。
6.最后返回area作為當前位置的活動區域的網格點數目。
7.定義主函數main，在main函數中首先讀取輸入的網格大小m和n，并創建一個二維vector grid用于存儲網格。
8.通過嵌套循環讀取每個網格的數值，并將其存儲在grid中。
9.調用maxGridArea函數計算最大活動區域的網格點數目，并將結果輸出到標準輸出流中。
10.返回0，表示程序執行完畢。

?C++代碼

#include <iostream>
#include <vector>
using namespace std;int dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {int m = grid.size();int n = grid[0].size();int area = 1;  // 活動區域的網格點數目，初始為1visited[i][j] = true;  // 將當前網格標記為已訪問vector<pair<int, int>> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};  // 上下左右四個方向的偏移量// 深度優先搜索for (auto direction : directions) {int dx = direction.first;int dy = direction.second;int nx = i + dx;int ny = j + dy;if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && abs(grid[nx][ny] - grid[i][j]) <= 1) {// 如果相鄰網格滿足條件（編號差值的絕對值小于等于1），則繼續搜索area += dfs(grid, nx, ny, visited);}}return area;
}int maxGridArea(vector<vector<int>>& grid) {int m = grid.size();  // 網格的行數int n = grid[0].size();  // 網格的列數int maxArea = 0;  // 最大活動區域的網格點數目// 創建一個與網格大小相同的二維數組，用于記錄已訪問的網格vector<vector<bool>> visited(m, vector<bool>(n, false));// 遍歷網格的每個位置作為起點for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j]) {int area = dfs(grid, i, j, visited);  // 深度優先搜索計算當前起點的活動區域的網格點數目maxArea = max(maxArea, area);  // 更新最大活動區域的網格點數目}}}return maxArea;
}int main() {int m, n;cin >> m >> n;vector<vector<int>> grid(m, vector<int>(n));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> grid[i][j];}}int maxArea = maxGridArea(grid);cout << maxArea << endl;return 0;
}