首页 > 其他分享 >The Lakes

The Lakes

时间:2024-01-05 20:45:37浏览次数:27  
标签:int 染色 Lakes main 可达性 总和

The Lakes

本质上是个染色问题,太久没写搜索,出现了错误。

最初做法

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

相关文章

  • CF1846E2 Rudolf and Snowflakes (hard version) 题解
    题意:\(T\)\((\)\(1\)\(\le\)\(T\)\(\le\)\(10^4\)\()\)组询问:是否存在一个满\(k\)(\(k\)\(\ge\)\(2\)\()\)叉树节点数恰好为\(n\)\((\)\(1\)\(\le\)\(n\)\(\le\)\(10^{18}\)\()\),且深度\(depth\)至少为\(2\)。思路:满$k$......
  • Snowflake Snow Snowflakes[PKUOJ 3349]
    这是一道蓝书上的哈希例题。相对简单。题面DescriptionYoumayhaveheardthatnotwosnowflakesarealike.Yourtaskistowriteaprogramtodeterminewhetherthisisreallytrue.Yourprogramwillreadinformationaboutacollectionofsnowflakes,andsear......
  • LAKESPY Outdoors Life
     LAKESPYWelcometo LAKESPY OutdoorsLife. [email protected]. Youcanalsovisitourwebsite:www.lakespy.com......
  • ​​Pyflakes
    Pyflakes是Python的一个分析包,可用来分析代码,发现各种潜在的问题,例如:引入但没有用到的模块,定义了但后面没有用到的变量等。使用Pyflakes分析代码风格和寻找违法PEP-8编码规范的地方是相当简单的;Pyflakes的另一优势是分析速度快,但它能报告的错误类型是相当有限的123。1:【脚本语言......
  • 为teamcity的代码语法检查工具pyflakes增加支持python2和python3
    TeamCity和pyflakesTeamCity是一款由JetBrains公司开发的持续集成和部署工具,它提供了丰富的功能来帮助团队协作进行软件开发。其中包括代码检查、自动化构建、测试运行、版本控制等多个方面。在我们团队中使用TeamCity进行配合pyflakes代码检查,我们需要升级pyflakes到支持python......
  • Unique Snowflakes uva11572
    找最长的,没有相同元素的区间 双指针#include<iostream>#include<set>usingnamespacestd;constintN=1e6+2;intn,a[N];voidsolve(){ intx=1,y=1,ans=0; set<int>st; while(y<=n){ while(y<=n&&!st.count(a[y]))s......