UVa 10651 - Pebble Solitaire 상태 압축 dp
Pebble solitaire is an interesting game. This is a game where you are given a board with an arrangement of small cavities, initially all but one occupied by a pebble each. The aim of the game is to remove as many pebbles as possible from the board. Pebbles disappear from the board as a result of a move. A move is possible if there is a straight line of three adjacent cavities, let us call them A, B, and C, with B in the middle, where A is vacant, but B and C each contain a pebble. The move constitutes of moving the pebble from C to A, and removing the pebble in Bfrom the board. You may continue to make moves until no more moves are possible.
In this problem, we look at a simple variant of this game, namely a board with twelve cavities located along a line. In the beginning of each game, some of the cavities are occupied by pebbles. Your mission is to find a sequence of moves such that as few pebbles as possible are left on the board.
Input
The input begins with a positive integer n on a line of its own. Thereafter n different games follow. Each game consists of one line of input with exactly twelve characters, describing the twelve cavities of the board in order. Each character is either '-' or 'o' (The fifteenth character of English alphabet in lowercase). A '-' (minus) character denotes an empty cavity, whereas a 'o' character denotes a cavity with a pebble in it. As you will find in the sample that there may be inputs where no moves is possible.
Output
For each of the n games in the input, output the minimum number of pebbles left on the board possible to obtain as a result of moves, on a row of its own.
Sample Input Output for Sample Input
5 ---oo------- -o--o-oo---- -o----ooo--- oooooooooooo oooooooooo-o
1 2 3 12 1
----------------------------------------------------------
아, 오랜만에 컨디션을 맞췄네.
검은색은 1이고 흰색은 0입니다.
f[x]는 상태 x가 완성할 수 있는 최대 변환수를 나타낸다.f[x]=max(f[t]+1)(x는 t에 도달 가능)
검은색 개수 - f[x]가 답이다.
-----------------------------------------------------------
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//110=6 001=1 011=3 100=4
int f[1<<12];
int tmp;
int dfs(int x)
{
//cerr<<"x= "<<x<<endl;
//getchar();
if (f[x]!=-1) return f[x];
int ret=0;
for (int i=0;i<10;i++)
{
int t=x;
if ( (x&(1<<(i+2))) && (x&(1<<(i+1))) && (x&(1<<i))==0 )
{
t^=(6<<i);
t|=(1<<i);
//cerr<<"check ok x= "<<x<<" i= "<<i<<" 6<<i= "<<(6<<i)<<" t="<<t<<endl;
ret=max( ret, dfs(t)+1 );
}
t=x;
if ( (x&(1<<(i+2)))==0 && (x&(1<<(i+1))) && (x&(1<<i)) )
{
t^=(3<<i);
t|=(4<<i);
//cerr<<"check ok x= "<<x<<" t="<<t<<endl;
ret=max( ret, dfs(t)+1 );
}
}
f[x]=ret;
return ret;
}
int main()
{
int T;
char s[20];
int black,bit;
memset(f,-1,sizeof(f));
scanf("%d",&T);
while (T--)
{
bit=0;
black=0;
scanf("%s",s);
for (int i=0;s[i];i++)
{
if (s[i]=='o')
{
bit|=(1<<i);
black++;
}
}
//
int ans=dfs(bit);
printf("%d
",black-ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.