正文 

当前位置： 首页 > java > java框架

[codevs1050]棋盘染色2（状态压缩dp）

Sakits      2022-02-17     335

关键词：

      题目大意：有一个5*N(≤100)的棋盘，棋盘中的一些格子已经被染成了黑色，求最少对多少格子染色，所有的黑色能连成一块。

      这题卡了我1h，写了2.6k的代码，清明作业一坨还没做啊。。。之前一直以为这题是插头DP，结果今天一看发现不用>_<，虽然还是状压DP。

      因为只有5列，所以每行至多有3个黑色联通块，即黑，白，黑，白，黑，其他的情况都少于3个联通块了，所以我们可以把联通块标号。0表示白色，1表示1号联通块，2和3同理，所以我们可以用4进制来表示每一行的状态。则下一行的黑色若与上一行的黑色连接，它的联通块编号即上一行与其连接的黑色的联通块编号。对于每一个状态，枚举下一层要涂黑哪个白色，然后转移，最后一层所有黑色为同一联通块就更新答案。这样这道题就做完了，思路很简单，但是写起来确实有点麻烦。。。不过写那么久一定是我太弱了= =。。。

代码如下：

技术分享 
type
  node=array[0..6]of longint;
var
  f:array[0..100,0..2000]of longint;
  a:array[0..100]of longint;
  h:array[0..102400,1..2]of longint;
  s,t:node;
  ch:char;
  n,i,j,ans:longint;

function lowbit(x:longint):longint;
begin
  if x=0 then exit(0);
  exit(lowbit(x-(x and -x))+1);
end;

procedure change(var a:node;sum1,sum2:longint);
var
  i:longint;
begin
  for i:=1 to 5 do
  if a[i]=sum1 then
  begin
    a[i]:=sum2;
    if (a[i-1]<>0)and(a[i-1]<10) then change(a,a[i-1],sum2);
    if (a[i+1]<>0)and(a[i+1]<10) then change(a,a[i+1],sum2);
  end;
end;

procedure work(var a:node);
var
  i,sum:longint;
begin
  sum:=10;
  for i:=1 to 5 do
  if (a[i]<>0)and(a[i]<10) then
  begin
    inc(sum);
    change(a,a[i],sum);
  end;
  for i:=1 to 5 do
  if a[i]>0 then dec(a[i],10);
end;

procedure bfs;
var
  i,j,k,yy,front,rear:longint;
  flag:boolean;
begin
  h[1][1]:=0;h[1][2]:=0;
  front:=0;rear:=1;
  while front<rear do
  begin
    inc(front);
    yy:=h[front][2];
    for i:=1 to 5 do
    begin
      s[i]:=h[front][2] and 3;
      h[front][2]:=h[front][2]>>2;
    end;
    h[front][2]:=yy;
    if h[front][1]=n then
    begin
      flag:=true;
      for i:=1 to 5 do
      if s[i]>1 then flag:=false;
      if flag then
      if ans>f[h[front][1],h[front][2]] then ans:=f[h[front][1]][h[front][2]];
      continue;
    end;
    for i:=0 to (1<<5)-1 do
    if i and a[h[front][1]+1]=0 then
    begin
      for j:=1 to 5 do
      t[j]:=(((a[h[front][1]+1]+i)>>(j-1))and 1)*(j+3);
      k:=0;
      for j:=1 to 5 do
      if (s[j]>0) and (t[j]>0) then
      begin
        t[j]:=s[j];
        k:=k or (1<<s[j]);
      end;
      flag:=true;
      for j:=1 to 5 do
      if (s[j]>0)and(k and (1<<s[j])=0) then flag:=false;
      if flag=false then continue;
      work(t);
      k:=0;
      for j:=5 downto 1 do
      k:=k<<2+t[j];
      if f[h[front][1]+1,k]>1000000000 then
      begin
        inc(rear);
        h[rear][1]:=h[front][1]+1;
        h[rear][2]:=k;
      end;
      if f[h[front][1]+1][k]>f[h[front][1]][h[front][2]]+lowbit(i) then
      f[h[front][1]+1][k]:=f[h[front][1]][h[front][2]]+lowbit(i);
    end;
  end;
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    for j:=1 to 5 do
    begin
      read(ch);
      if ch=‘1‘ then a[i]:=a[i] or 1<<(j-1);
    end;
    readln;
  end;
  while n>0 do
  begin
    if a[n]>0 then break;
    dec(n);
  end;
  if n=0 then
  begin
    writeln(0);
    halt;
  end;
  fillchar(f,sizeof(f),63);
  t[0]:=0;t[6]:=0;
  ans:=maxlongint;
  f[0,0]:=0;
  bfs;
  writeln(ans);
end.
View Code

       看样子我的代码在Pascal党里算是很短的了。。。而且我的代码还有饱受机房神犇吐槽的begin打在下一行，如下图，代码长度在最后一栏

技术分享

[codevs]1014棋盘染色

1049棋盘染色 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold 题目描述 Description有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑... 查看详情

[codevs1049]棋盘染色

[codevs1049]棋盘染色试题描述有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且你染色的格子数目要最少。读入一个初始棋盘的... 查看详情

codevs1049棋盘染色

1049棋盘染色  时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解   题目描述 Description有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染... 查看详情

codevs——1049棋盘染色

1049棋盘染色  时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解 查看运行结果  题目描述 Description有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一... 查看详情

codevs——t1049棋盘染色

...运行结果  题目描述 Description有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑色格子能连成一块，并且 查看详情

codevs1049棋盘染色

题目大意：01矩阵，1表示黑色，0表示白色，求将白色染成黑色最少的次数使黑色成为一整个联通块。题解：搜索bfs90...dfs判断连通#include<iostream>#include<cstdio>#include<cstring>#include<queue>usingnamespacestd;intcnt,ans,flag;intma... 查看详情

codevs2853方格游戏--棋盘dp(代码片段)

方格游戏：http://codevs.cn/problem/2853/ 这和传纸条和noip方格取数这两个题有一定的相似性，当第一眼看到的时候我们就会想到设计$dp[i][j][k][l]$(i,j表示一个人走到i行j个点，而另一个人走到k行第l个点)这么一个状态。转移方程当... 查看详情

dp状态压缩之棋盘问题(代码片段)

写在前面状态压缩的思想是将难以用机器语言表达具象的现实实物进行抽象.常常用二进制数来表达一种状态比方说有A、B、C，三个方案，2=010表示不选A，选B，不选C的方案，于是要枚举所有方案只需要枚举0... 查看详情

[codefoeces398b]paintingthewall(概率dp)

 题目大意：一个$n imesn$的棋盘，其中有$m$个格子已经被染色，执行一次染色操作(无论选择的格子是否已被染色)消耗一个单位时间，染色时选中每个格子的概率均等，求使每一行、每一列都存在被染色的格子的期望用时。&nbs... 查看详情

cf1051d简单的状态压缩dp(代码片段)

/*给定一个二行n列的格子，在里面填黑白色，要求通过黑白色将格子分为k块请问有多少种填色方式dp[j][k][0,1,2,3]填到第j列，有k块，第j列的颜色，*/#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definemod998244353//0全白，1黑白，2... 查看详情

codevs1358棋盘游戏(状压dp)

1358棋盘游戏  时间限制:1s 空间限制:64000KB 题目等级:大师Master  题目描述 Description这个游戏在一个有10*10个格子的棋盘上进行，初始时棋子位于左上角，终点为右下角，棋盘上每个格子内有一个0到9的数... 查看详情

codevs1922骑士共存问题（最小割，二分图最大匹配）

题意：在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它... 查看详情

codevs——1169传纸条（棋盘dp）

2008年NOIP全国联赛提高组 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中... 查看详情

codevs——2853方格游戏（棋盘dp）

 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 题目描述 Description菜菜看到了一个游戏，叫做方格游戏~游戏规则是这样的：在一个n*n的格子中，在每个1*1的格子里都能获得一定数量的积分奖励，记左上... 查看详情

状态压缩dp初探(代码片段)

状态压缩DP初探+++1.蒙德里安的梦想求把NM的棋盘分割成若干个12的的长方形，有多少种方案。例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。如下图所示：输入格式输入包含多组测试用例。每组测试用例占一行，包... 查看详情

炮（棋盘dp）

...　一直以为自己写的就是状态压缩，结果写完才知道是个棋盘dp　　首先看一下题目　　嗯，象棋，还是只有炮的象棋　　对于方案数有几种，我第一个考虑是dfs，但是超时稳稳的，所以果断放弃　　然后记得以前有过和这个题... 查看详情

棋盘染色2

传送门题目描述 Description有一个5*N的棋盘，棋盘中的一些格子已经被染成了黑色，你的任务是对最少的格子染色，使得所有的黑色能连成一块。输入描述 InputDescription第一行一个整数N(<=100)，接下来N行每行一个长度为5... 查看详情

宽度优先搜索神奇的状态压缩codevs1004四子连棋

...有什么难度。博主写这篇blog主要是想写下一个想法——状态压缩。状态压缩在记录、修改状态以及判重去重等方面有着极高的（←_←词穷了，诸位大致理解一下就好）效率。博主原本打算在blog介绍一种DP——状态压缩型动态规... 查看详情