---

E. The Lakes

原创 已于 2023-08-12 02:18:33 修改 · 粉丝可见 · 202 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132211572

题目：

cobol<br/>5<br/>3 3<br/>1 2 0<br/>3 4 0<br/>0 0 5<br/>1 1<br/>0<br/>3 3<br/>0 1 1<br/>1 0 1<br/>1 1 1<br/>5 5<br/>1 1 1 1 1<br/>1 0 0 0 1<br/>1 0 5 0 1<br/>1 0 0 0 1<br/>1 1 1 1 1<br/>5 5<br/>1 1 1 1 1<br/>1 0 0 0 1<br/>1 1 4 0 1<br/>1 0 0 0 1<br/>1 1 1 1 1<br/>

cobol<br/>10<br/>0<br/>7<br/>16<br/>21<br/>

思路：

BFS或者 DFS 走一遍，这里都是只用一次数值，所以我们每当取完这个数值之后，都可以赋值为 0 ，就可以边走边初始化的操作，我就是没想到这个一直 TLE (;´༎ຶД༎ຶ`)

所以AC代码如下：

#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define x first
#define y second
#define mk make_pair
#define umap unordered_map
#define endl '\n'
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
const int N = 1e4 + 10;
 
int n, m;	// 湖泊图大小
 
umap<int, int>g[N];	// 湖泊图数值
int step;
inline void DFS(int x, int y)
{
	if (!g[x][y])
		return ;
	step += g[x][y];
	g[x][y] = 0;
	for (int i = 0; i < 4; ++i)
	{
		int bx = x + dx[i];
		int by = y + dy[i];
		DFS(bx, by);
	}
	return ;
}
 
inline void solve()
{
	int ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> g[i][j];
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (g[i][j])
			{
				step = 0;
				DFS(i, j);
				ans = max(ans, step );
			}
		}
	}
	cout << ans << endl;
}
 
int main()
{
	___G;
//	freopen("a.txt", "r", stdin);
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：