当前位置：首页 > news >正文

E - Red Polyomino 关于回溯和爆搜

news 来源：原创 2024/9/20 7:27:51

这题就是爆搜。。虽然看似有2^(nn)的复杂度。。
但是实际上因为相连的限制。。种类非常有限。。样例88的就可以看出来。
所以就是爆搜而已。。

记录这题是因为。之前一直在思考回溯到底和爆搜什么关系。。
目前算是阶段性的一个理解。。
回溯只不过是爆搜的一种方式而已。。
如果我们可以每层递归都是拷贝。而不是引用。。实际上是不需要回溯的。

回溯只在于样本只有一份。就是传引用的时候。我们只有通过恢复现场。。来尝试其他的可能。
下面两个版本的写法。。就证明了这点。。
总结：回溯只不过是恢复现场的一种手法。。如果现场不需要恢复（每层都拷贝一份新的）就不需要回溯🔥
而爆搜是一种枚举所有可能的手法。。分步X分类。比较经典的爆搜模型就是完全二叉树每个节点两种可能选和不选。
题目链接

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
int ans;
void dfs(vector<string>s) {int cnt = 0;for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {cnt += s[i][j] == 'o';}if (cnt == k) {ans++;return ;}for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {if (s[i][j] != '.')continue;if (cnt) {int d[5] {1, 0, -1, 0, 1};bool ok = 0;for (int c = 0; c < 4; ++c) {int x = i + d[c], y = j + d[c + 1];if (x >= 0 && y >= 0 && x < n && y < n && s[x][y] == 'o')ok = 1;}if (ok == 0)//就是旁边一定要有红色的。。因为相连continue;}s[i][j] = 'o';dfs(s);s[i][j] = '#';dfs(s);//我们传的是整个拷贝的s。这边就不需要回溯。return ;}
}
void solve() {cin >> n >> k;vector<string>a(n);for (auto&a : a)cin >> a;dfs(a);cout << ans;
};signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
int ans;
void dfs(vector<string>&s) {int cnt = 0;for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {cnt += s[i][j] == 'o';}if (cnt == k) {ans++;return ;}for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {if (s[i][j] != '.')continue;if (cnt) {int d[5] {1, 0, -1, 0, 1};bool ok = 0;for (int c = 0; c < 4; ++c) {int x = i + d[c], y = j + d[c + 1];if (x >= 0 && y >= 0 && x < n && y < n && s[x][y] == 'o')ok = 1;}if (ok == 0)//就是旁边一定要有红色的。。因为相连continue;}s[i][j] = 'o';dfs(s);s[i][j] = '#';dfs(s);s[i][j] = '.';//回溯本质上就多了这一步而已。。但是可以传引用。。！！！！return ;}
}
void solve() {cin >> n >> k;vector<string>a(n);for (auto&a : a)cin >> a;dfs(a);cout << ans;
};// 回溯只不过是为了还原现场而已。。如果传的不是引用。。。每个图都拷贝一份。那么根本不需要回溯！！！
//回溯只不过是爆搜的一种实现策略。。而已。。每个图都拷贝一份。那么根本不需要回溯！
// signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}