题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#define x first
#define y second
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N = 11,p = 1331;
PII u[N*N];
int w[N][N],f[N*N],sum = 0,n,m,ans = 1e8;
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
bool st[N][N];
unordered_set<ULL> H;
int find(int x)
{
if(f[x]!=x) return f[x] = find(f[x]);
return f[x];
}
bool check_1(int k)
{
static PII backup[N*N];
for(int i=0;i<k;i++) backup[i] = u[i];
sort(backup,backup+k);
ULL x = 0;
for(int i=0;i<k;i++)
{
x = x*p + backup[i].x + 1;
x = x*p + backup[i].y + 1;
}
if(H.count(x)) return true;
H.insert(x);
return false;
}
bool check_2(int k)
{
int cnt = n*m - k;
for(int i=1;i<n*m;i++) f[i] = i;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(st[i][j]) continue;
for(int u=0;u<4;u++)
{
int a = i+dx[u],b = j+dy[u];
if(a<0||a>=n||b<0||b>=m||st[a][b]) continue;
int p1 = find(a*m+b),p2 = find(i*m+j);
if(p1!=p2)
{
cnt--;
f[p1] = p2;
}
}
}
}
if(cnt>1) return false;
return true;
}
void dfs(int s,int k)
{
if(s==sum/2)
{
if(check_2(k)) ans = min(ans,k);
return;
}
if(k+1>=ans) return;
for(int i=0;i<k;i++)
{
int x = u[i].x,y = u[i].y;
for(int i=0;i<4;i++)
{
int a = x+dx[i],b = y+dy[i];
if(a<0||a>=n||b<0||b>=m||st[a][b]) continue;
u[k] = {a,b};
if(!check_1(k+1)&&s+w[a][b]<=sum/2)
{
st[a][b] = true;
dfs(s+w[a][b],k+1);
st[a][b] = false;
}
}
}
}
int main()
{
cin >> m >> n;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin >> w[i][j];
sum += w[i][j];
}
if(sum%2==0)
{
u[0] = {0,0};
st[0][0] = true;
dfs(w[0][0],1);
}
if(ans==1e8) ans = 0;
cout << ans << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla