本质上是个染色问题,太久没写搜索,出现了错误。
最初做法
int main()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (vis[i][j] == false && a[i][j] != 0)
{vis[i][j] = true; dfs(i, j, a[i][j]);}
}
}
}
void dfs(int x, int y, long sum)
{
ans = max(sum, ans);
for (int i = 0; i < 4; i++)
{
int dx = x + move[i][0], dy = y + move[i][1];
if (check(dx, dy) == true)
{
vis[dx][dy] = true;
dfs(dx, dy, sum + a[dx][dy]);
}
}
}
不回溯的想法没问题,因为是可达性不是路径问题。
但是偏偏计算总和的时候,就忘了这是可达性。
显然,该函数计算的总和是一条路径的总和,而非一块染色的总和。
改成计算所有到达的权值和即可。
正确做法
int main()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (vis[i][j] == false && a[i][j] != 0)
{sum = 0; vis[i][j] = true; dfs(i, j); ans = max(sum, ans);}
}
}
}
void dfs(int x, int y)
{
sum += a[x][y];
for (int i = 0; i < 4; i++)
{
int dx = x + move[i][0], dy = y + move[i][1];
if (check(dx, dy) == true)
{
vis[dx][dy] = true;
dfs(dx, dy);
}
}
}
标签:int,染色,Lakes,main,可达性,总和
From: https://www.cnblogs.com/kdlyh/p/17948045