HDu 1882 Strange Billboard(ビット演算+列挙)
http://acm.hdu.edu.cn/showproblem.php?pid=1882
いい問題だと思います.
n*m(1<=n,m<=16)の行列を与え、各格子には白黒の両面があり、1つの格子をひっくり返すと上下左右が反転し、最後に格子をすべて白色にする最小反転ステップ数を聞く.
第1行の状態を列挙するだけでよい.第i(i>=2)行j列の反転については前の行の制約を受けるため、前の行も「X」の場合にのみ、その行j列が反転し、i-1行j列が「.」になる.そうしないと、i行j列は反転できない.順番に進み、最後の行がすべて白くなると、反転に成功したことを示します.
1つの重要な最適化:n280 ms走って、他の人のブログを見て、彼は行を反転したはずです.しかし、そのビット演算は、分からない...
いい問題だと思います.
n*m(1<=n,m<=16)の行列を与え、各格子には白黒の両面があり、1つの格子をひっくり返すと上下左右が反転し、最後に格子をすべて白色にする最小反転ステップ数を聞く.
第1行の状態を列挙するだけでよい.第i(i>=2)行j列の反転については前の行の制約を受けるため、前の行も「X」の場合にのみ、その行j列が反転し、i-1行j列が「.」になる.そうしないと、i行j列は反転できない.順番に進み、最後の行がすべて白くなると、反転に成功したことを示します.
1つの重要な最適化:n
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
int n,m;
char map[17][17];
int sta[17],tmp[17];
int bit[17];
int ans;
void cal()
{
bit[0] = 1;
for(int i = 1; i < 17; i++)
bit[i] = (bit[i-1] << 1);
}
void input()
{
memset(sta,0,sizeof(sta)); //
if(n >= m)
{
for(int i = 0; i < n; i++)
{
scanf("%s",map[i]);
for(int j = 0; j < m; j++)
{
if(map[i][j] == 'X')
sta[i] = (sta[i] << 1) + 1;
else sta[i] <<= 1;
}
}
}
// ， m < n
else
{
for(int i = 0; i < n; i++)
{
scanf("%s",map[i]);
for(int j = 0; j < m; j++)
{
if(map[i][j] == 'X')
sta[j] = (sta[j] << 1) + 1;
else sta[j] <<= 1;
}
}
swap(n,m);
}
}
void solve()
{
int step;
ans = INF;
for(int i = 0; i < (1<<m); i++)
{
memcpy(tmp,sta,sizeof(sta));
step = 0;
//
for(int j = 0; j < m && step < ans; j++)
{
if(bit[j]&i)
{
step++;
if(j > 0)
tmp[0] ^= bit[j-1];
if(j < m-1)
tmp[0] ^= bit[j+1];
tmp[0] ^= bit[j];
tmp[1] ^= bit[j];
}
}
// j-1 j
for(int j = 1; j < n && step < ans; j++)
{
for(int k = 0; k < m && step < ans; k++)
{
if(bit[k]&tmp[j-1])
{
step++;
if(k > 0)
tmp[j] ^= bit[k-1];
if(k < m-1)
tmp[j] ^= bit[k+1];
tmp[j] ^= bit[k];
tmp[j+1] ^= bit[k];
}
}
}
if(!tmp[n-1])
ans = min(ans,step);
}
}
int main()
{
cal();
while(~scanf("%d %d",&n,&m))
{
if(n == 0 && m == 0) break;
input();
solve();
if(ans == INF)
printf("Damaged billboard.
");
else printf("You have to tap %d tiles.
",ans);
}
return 0;
}