ACwing95 费解的开关 bfs

2021-01-29 04:12

阅读：406

标签：一个 $0 print 超时 bool https get ble c代码

网址：https://www.acwing.com/problem/content/97/

题意：

给出一个$5×5$的$01$矩阵，翻转一个点时，其上下左右合法的点都会被翻转，给出一个状态，问你能不能在$6$步的范围内使所有的元素都变成$1$。每个测试点最多$500$组数据。

题解：

如果直接$dfs$，那么对于一个矩阵，其时间复杂度是$O(C^{6}_{25})$，$500$个矩阵就会超时，所以我们使用一个队列进行$bfs$，记录$bfs$的层数。记录的方法是，对于一个没有出现过的局势，其层数为转移得到这个状态的状态的层数$+1$并压入队列，然后一旦队列中出现这个状态的层数是$6$则退出（这意味着队列中其他的状态都是$6$，其再进行$bfs$将会记录翻转了$7$次的状态，而这个不合法）。然后读入这些状态，判断其$bfs$的层数即可。

AC代码：

#include 
using namespace std;
int mp[1  4 || y  4)
		return 0;
	return 1;
}
int _hash(int x, int i)
{
	int px = i / 5, py = i % 5;
	for (int i = 0; i que;
	mp[(1

ACwing95 费解的开关 bfs

标签：一个 $0 print 超时 bool https get ble c代码

原文地址：https://www.cnblogs.com/Aya-Uchida/p/11872879.html

上一篇：C# 消息队列之 RabbitMQ 入门基础

下一篇：win api 音频可视化

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ACwing95 费解的开关 bfs
文章链接：http://soscw.com/index.php/essay/48512.html

亲，登录后才可以留言！

ACwing95 费解的开关 bfs

题意：

题解：

评论

热门文章

推荐文章

最新文章

置顶文章