华为OD机试【机器人活动区域】

题目描述

现有一个机器人，可放置于 M x N 的网格中任意位置

每个网格包含一个非负整数编号，

当相邻网格的数字编号差值的绝对值小于等于 1 时

机器人可以在网格间移动。

问题: 求机器人可活动的最大范围对应的网格点数目。

说明:

网格左上角坐标为(0,0),右下角坐标为(m - 1,n - 1)机器人只能在相邻网格间上下左右移动

输入描述

第 1 行入为 M 和， 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

DFS

#include <bits/stdc++.h>
using namespace std;

int m, n;
void dfs(int i, int j, vector<vector<int>> v,vector<vector<int>> &rd,int &tmp) {
	int a = v[i][j];
	rd[i][j]++;
	tmp++;
	if (i + 1 < m && rd[i + 1][j]==0 && abs(v[i+1][j] - a) <= 1)//继续DFS条件都是不超过边界&&该点未访问过&&差值<=1
		dfs(i+1, j, v, rd,tmp);
	if (i - 1 >= 0 && rd[i - 1][j] == 0 && abs(v[i-1][j] - a) <= 1)
		dfs(i-1, j, v, rd,tmp);
	if (j + 1 < n && rd[i][j + 1] == 0 && abs(v[i][j+1] - a) <= 1)
		dfs(i, j+1, v, rd, tmp);
	if (j - 1 >= 0 && rd[i][j - 1] == 0 && abs(v[i][j-1] - a) <= 1)
		dfs(i, j-1, v, rd, tmp);
}

int main() {
	int count=0;
	cin >> m >> n;
	vector<vector<int>>v(m,vector<int>(n));
	vector<vector<int>>rd(m, vector<int>(n,0));//记录点是否被访问过
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (rd[i][j] == 0) {
				vector<vector<int>>rd(m, vector<int>(n, 0));//重置记录数组
				int tmp=0;//tmp用于记录该次DFS所得可行走范围大小
				dfs(i, j, v, rd, tmp);
				}
			count = max(count, tmp);//记录最大可行走范围
		}
	}
	cout << count;
}

增加一个RD2记录数组减少递归次数

void dfs(int i, int j, vector<vector<int>> v,vector<vector<int>> &rd, vector<vector<int>> &rd2,int &tmp) {
	int a = v[i][j];
	rd[i][j]++; rd2[i][j]++;
	tmp++;
	if (i + 1 < m && rd[i + 1][j]==0 && abs(v[i+1][j] - a) <= 1)
		dfs(i+1, j, v, rd,rd2,tmp);
	if (i - 1 >= 0 && rd[i - 1][j] == 0 && abs(v[i-1][j] - a) <= 1)
		dfs(i-1, j, v, rd,rd2,tmp);
	if (j + 1 < n && rd[i][j + 1] == 0 && abs(v[i][j+1] - a) <= 1)
		dfs(i, j+1, v, rd,rd2, tmp);
	if (j - 1 >= 0 && rd[i][j - 1] == 0 && abs(v[i][j-1] - a) <= 1)
		dfs(i, j-1, v, rd,rd2, tmp);
}

int main() {
	int count=0;
	cin >> m >> n;
	vector<vector<int>>v(m,vector<int>(n));
	vector<vector<int>>rd(m, vector<int>(n, 0));
	vector<vector<int>>rd2(m, vector<int>(n, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (rd2[i][j] == 0) {
				vector<vector<int>>rd(m, vector<int>(n, 0));
				int tmp = 0;
				dfs(i, j, v, rd,rd2, tmp);
				count = max(count, tmp);
		}
		}
	}
	cout << count;
}