SMOJ 一笔画/洛谷 P7171 COCI 2020/2021 #3 Selotejp 题解

1.一笔画

题意

给出 n 行 m 列的点阵，每个点是一个字符： “.” 或 “#” ，其中“#”表示该点是障碍物。

现在小毛的问题是： 他最少要画多少笔才能把点阵里所有的“.”都覆盖完毕（被小毛画到的点就会被覆盖）。

小毛每次只能在某一行或某一列画，小毛当然想一笔就把某一行或某一列画完，

但很遗憾，在任何时候都不允许小毛画的那一段点阵含有障碍物。

还有一点更奇怪： 已经被画过的点，不能重复被画。

问小毛最少要画多少笔？

$0<n,m\le 15$

2.Selotejp

两个字符的含义交换，数据范围改成$1\le n\le 1000，1\le m\le 10$

思路

非常复杂的一道题。

我们发现$n,m$中有一个尤其小，那么可以想到对每一行的状态压缩

我们钦定$m$位状态$s$，每一位上，$0$ 表示填横线或者有障碍物，$1$表示填竖线。如果到了右侧边界，直接转移到下一行第一个，继承这个行状态，表示该行$r$对下一行$r+1$的影响。

考虑一行一行处理，对于$r$行$c$列的格子，分情况考虑怎么画这个格子。

先明确：下文讲提到本位$c$和上一位（左边）$c-1$，在代码中它们的状态表示为：

int t=(1<<(c-1)),pt=(1<<(c-1-1));//t本位 pt上一位 

障碍物

如果这个格子是一个障碍物，那么状态$s$上的这一位理应填$0$，需要强制把它修改为$0$，因为不会从这个障碍物伸出一条竖线影响下一行了。之后向下一位转移。

if(a[r][c]=='#')//障碍物 
{if((s&t)==t)f[r][c][s]=dfs(r,c+1,s^t);//去1 else f[r][c][s]=dfs(r,c+1,s);return f[r][c][s];
}

填竖线

如果上一行继承下来的状态，该为$c$为$1$，那么可以直接利用这条现成的竖线；否则需要多加一条竖线，把该位强制修改为$1$，并记得加上$1$。

if((s&t)==t)shu=dfs(r,c+1,s);//s的c位是1，利用现有的竖线 
else shu=dfs(r,c+1,s|t)+1;//新建一条竖线 

填横线

如果左边$c-1$位不是障碍物，且上一位$c-1$位填了$0$，说明$c$位左边有一条现成的横线，可以直接利用，并将该位$c$强制修改为$0$。

否则就需要在这一位新开一条横线，并将该位$c$强制修改为$0$。

if(a[r][c-1]=='.'&&!((s&pt)==pt))//上一个不是障碍物，且上一个填了横线 
{if((s&t)==t)heng=dfs(r,c+1,s^t);//原本是竖线 else heng=dfs(r,c+1,s);//本来就是横线 
}
else //上一个是障碍物，要新建一条横线 
{if((s&t)==t)heng=dfs(r,c+1,s^t)+1;else heng=dfs(r,c+1,s)+1;
}

换行、继承等操作，本人使用记忆化搜索。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=16,M=16,inf=0x3f3f3f3f;
int n,m;
char a[N][M];
int f[N][M][1<<M];
int dfs(int r,int c,int s)
{if(r>n)return 0;if(c>m)return dfs(r+1,1,s);//换行，把状态复制到下一行 if(!(f[r][c][s]>=inf))return f[r][c][s];int t=(1<<(c-1)),pt=(1<<(c-1-1));//t本位 pt上一位 if(a[r][c]=='#')//障碍物 {if((s&t)==t)f[r][c][s]=dfs(r,c+1,s^t);//去1 else f[r][c][s]=dfs(r,c+1,s);return f[r][c][s];}//竖 int heng=inf,shu=inf;if((s&t)==t)shu=dfs(r,c+1,s);//s的c位是1，利用现有的竖线 else shu=dfs(r,c+1,s|t)+1;//新建一条竖线 if(a[r][c-1]=='.'&&!((s&pt)==pt))//上一个不是障碍物，且上一个填了横线 {if((s&t)==t)heng=dfs(r,c+1,s^t);//原本是竖线 else heng=dfs(r,c+1,s);//本来就是横线 }else //上一个是障碍物，要新建一条横线 {if((s&t)==t)heng=dfs(r,c+1,s^t)+1;else heng=dfs(r,c+1,s)+1;}f[r][c][s]=min(heng,shu);return f[r][c][s];
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];memset(f,inf,sizeof(f));printf("%d",dfs(1,1,0));return 0;
}

第$2$题的代码敬请自行修改