网站的根目录的路径,定制旅游网站建设方案,东莞设计网站,开发云app1.一笔画
题意
给出 n 行 m 列的点阵#xff0c;每个点是一个字符#xff1a; “.” 或 “#” #xff0c;其中“#”表示该点是障碍物。
现在小毛的问题是#xff1a; 他最少要画多少笔才能把点阵里所有的“.”都覆盖完毕#xff08;被小毛画到的点就会被覆盖#xff…1.一笔画
题意
给出 n 行 m 列的点阵每个点是一个字符 “.” 或 “#” 其中“#”表示该点是障碍物。
现在小毛的问题是 他最少要画多少笔才能把点阵里所有的“.”都覆盖完毕被小毛画到的点就会被覆盖。
小毛每次只能在某一行或某一列画小毛当然想一笔就把某一行或某一列画完
但很遗憾在任何时候都不允许小毛画的那一段点阵含有障碍物。
还有一点更奇怪 已经被画过的点不能重复被画。
问小毛最少要画多少笔 0 n , m ≤ 15 0 n, m \le15 0n,m≤15
2.Selotejp
两个字符的含义交换数据范围改成 1 ≤ n ≤ 1000 1 ≤ m ≤ 10 1≤n≤10001≤m≤10 1≤n≤10001≤m≤10
思路
非常复杂的一道题。
我们发现 n , m n,m n,m中有一个尤其小那么可以想到对每一行的状态压缩
我们钦定 m m m位状态 s s s每一位上 0 0 0 表示填横线或者有障碍物 1 1 1表示填竖线。如果到了右侧边界直接转移到下一行第一个继承这个行状态表示该行 r r r对下一行 r 1 r1 r1的影响。
考虑一行一行处理对于 r r r行 c c c列的格子分情况考虑怎么画这个格子。
先明确下文讲提到本位 c c c和上一位左边 c − 1 c-1 c−1在代码中它们的状态表示为
int t(1(c-1)),pt(1(c-1-1));//t本位 pt上一位 障碍物
如果这个格子是一个障碍物那么状态 s s s上的这一位理应填 0 0 0需要强制把它修改为 0 0 0因为不会从这个障碍物伸出一条竖线影响下一行了。之后向下一位转移。
if(a[r][c]#)//障碍物
{if((st)t)f[r][c][s]dfs(r,c1,s^t);//去1 else f[r][c][s]dfs(r,c1,s);return f[r][c][s];
}填竖线
如果上一行继承下来的状态该为 c c c为 1 1 1那么可以直接利用这条现成的竖线否则需要多加一条竖线把该位强制修改为 1 1 1并记得加上 1 1 1。
if((st)t)shudfs(r,c1,s);//s的c位是1利用现有的竖线
else shudfs(r,c1,s|t)1;//新建一条竖线 填横线
如果左边 c − 1 c-1 c−1位不是障碍物且上一位 c − 1 c-1 c−1位填了 0 0 0说明 c c c位左边有一条现成的横线可以直接利用并将该位 c c c强制修改为 0 0 0。
否则就需要在这一位新开一条横线并将该位 c c c强制修改为 0 0 0。
if(a[r][c-1].!((spt)pt))//上一个不是障碍物且上一个填了横线
{if((st)t)hengdfs(r,c1,s^t);//原本是竖线 else hengdfs(r,c1,s);//本来就是横线
}
else //上一个是障碍物要新建一条横线
{if((st)t)hengdfs(r,c1,s^t)1;else hengdfs(r,c1,s)1;
}换行、继承等操作本人使用记忆化搜索。
代码
#includebits/stdc.h
using namespace std;
const int N16,M16,inf0x3f3f3f3f;
int n,m;
char a[N][M];
int f[N][M][1M];
int dfs(int r,int c,int s)
{if(rn)return 0;if(cm)return dfs(r1,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((st)t)f[r][c][s]dfs(r,c1,s^t);//去1 else f[r][c][s]dfs(r,c1,s);return f[r][c][s];}//竖 int henginf,shuinf;if((st)t)shudfs(r,c1,s);//s的c位是1利用现有的竖线 else shudfs(r,c1,s|t)1;//新建一条竖线 if(a[r][c-1].!((spt)pt))//上一个不是障碍物且上一个填了横线 {if((st)t)hengdfs(r,c1,s^t);//原本是竖线 else hengdfs(r,c1,s);//本来就是横线 }else //上一个是障碍物要新建一条横线 {if((st)t)hengdfs(r,c1,s^t)1;else hengdfs(r,c1,s)1;}f[r][c][s]min(heng,shu);return f[r][c][s];
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j)cina[i][j];memset(f,inf,sizeof(f));printf(%d,dfs(1,1,0));return 0;
}第 2 2 2题的代码敬请自行修改
