NC15883. Brute Force!
描述
输入描述
There are two integers N and M(N+M≤25) in the first line, as described above.
Then there is an N×M grid followed, indicating the color of each grid. ‘#’ denotes black grid and ‘.’denotes white grid.
输出描述
Output the minimum grids you need to choose.
示例1
输入:
3 3 #.# .#. #.#
输出:
5
示例2
输入:
3 3 .#. ### .#.
输出:
1
C++14(g++5.4) 解法, 执行用时: 132ms, 内存消耗: 6368K, 提交时间: 2019-02-15 14:12:41
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int f[2][1000005],p[20];
int main()
{
int _,j,k,n,m;
p[0]=1;
for(_=1;_<=15;_++)
p[_]=p[_-1]*3;
char s[50][50],str[50][50];
scanf("%d%d",&n,&m);
for(_=0;_<n;_++)
scanf("%s",&s[_]);
if(n<m)
{
for(_=0;_<n;_++)
for(j=0;j<m;j++)
str[j][_]=s[_][j];
memcpy(s,str,sizeof(str));
swap(n,m);
}
int now=0,last=1,cur,nxt;
memset(f[now],INF,sizeof(f[now]));
f[now][0]=0;
for(_=0;_<n;_++)
for(j=0;j<m;j++)
{
swap(last,now);
memset(f[now],INF,p[m]*sizeof(int));
for(k=0;k<p[m];k++)
if(f[last][k]<INF)
{
int cov=(k/p[j]%3==2);
if(j>0)
cov|=(k/p[j-1]%3==2);
if(s[_][j]=='#')
{
nxt=k-(k/p[j]%3*p[j]);
nxt+=2*p[j];
if(j>0&&(k/p[j-1]%3)<2)
{
nxt-=(k/p[j-1]%3*p[j-1]);
nxt+=p[j-1];
}
f[now][nxt]=min(f[now][nxt],f[last][k]+1);
}
if(_==0 || s[_-1][j]!='#' || (k/p[j]%3)!=0)
{
nxt=k-(k/p[j]%3*p[j]);
nxt+=cov*p[j];
f[now][nxt]=min(f[now][nxt],f[last][k]);
}
}
}
/*
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt45z4hrzhrhzhrehrthzthztbtzhtjzt45z4hrzhrhzhrehrthzthztbtzhtjzt45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt
45z4hrzhrhzhrehrthzthztbtzhtjzt45z4hrzhrhzhrehrthzthztbtzhtjzt
*/
int res=n*m;
for(_=0;_<p[m];_++)
{
bool isok=1;
for(j=0;j<m;j++)
isok&=(s[n-1][j]=='.' || _/p[j]%3>0);
if(isok)
res=min(res,f[now][_]);
}
printf("%d\n",res);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 112ms, 内存消耗: 6496K, 提交时间: 2020-03-18 12:39:26
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int dp[2][1000005],p[20];
int main()
{
int i,j,k,n,m;
p[0]=1;
for(i=1;i<=15;i++)
p[i]=p[i-1]*3;
char s[50][50],str[50][50];
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%s",&s[i]);
if(n<m)
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
str[j][i]=s[i][j];
memcpy(s,str,sizeof(str));
swap(n,m);
}
int now=0,last=1,cur,nxt;
memset(dp[now],INF,sizeof(dp[now]));
dp[now][0]=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
swap(last,now);
memset(dp[now],INF,p[m]*sizeof(int));
for(k=0;k<p[m];k++)
if(dp[last][k]<INF)
{
int cov=(k/p[j]%3==2);
if(j>0)
cov|=(k/p[j-1]%3==2);
if(s[i][j]=='#')
{
nxt=k-(k/p[j]%3*p[j]);
nxt+=2*p[j];
if(j>0&&(k/p[j-1]%3)<2)
{
nxt-=(k/p[j-1]%3*p[j-1]);
nxt+=p[j-1];
}
dp[now][nxt]=min(dp[now][nxt],dp[last][k]+1);
}
if(i==0||s[i-1][j]!='#'||(k/p[j]%3)!=0)
{
nxt=k-(k/p[j]%3*p[j]);
nxt+=cov*p[j];
dp[now][nxt]=min(dp[now][nxt],dp[last][k]);
}
}
}
int res=n*m;
for(i=0;i<p[m];i++)
{
bool isok=1;
for(j=0;j<m;j++)
isok&=(s[n-1][j]=='.'||i/p[j]%3>0);
if(isok)
res=min(res,dp[now][i]);
}
printf("%d\n",res);
return 0;
}