程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4012Paint on a Wall

HDU 4012Paint on a Wall

編輯:關於C++

 

Paint on a Wall

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65768/65768K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Problem Description Annie wants to paint her wall to an expected pattern. The wall can be represented as a 2*n grid and each grid will be painted only one color. Annie has a brush which could paint a rectangular area of the wall at a single step. The paint could be overlap and the newly painted color will replace the older one.
For a given pattern of the wall, your task is to help Annie find out the minimum possible number of painting steps. You can assume that the wall remains unpainted until Annie paint some colors on it.

Input There are multiple test cases in the input. The first line contains the number of test cases. For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8) Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter. See the sample input for further details.
Output For each test case, output only one integer denoting the minimum number of steps.
Sample Input
3
3
ABA
CBC
3
BAA
CCB
3
BBB
BAB

Sample Output
Case #1: 3
Case #2: 3
Case #3: 2

Source The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup

 

廣搜題目,枚舉起點,染色為對的顏色,然後向左至對的顏色,向右至對的顏色 然後上下兩行一起

狀態壓縮 每行最多八個點 所以2^16可以將狀態存儲

 

 

#include
#include
#include
#include
using namespace std;

int t,n,tt;
bool vis[2][8],tmp[2][8];
char ch[2][8];
bool flag[1<<16];//標記判重
struct node
{
    int flag;
    int t;
} st,ed;

void set_vis(node a)  //獲得狀態矩陣值
{
    memset(vis,false ,sizeof(vis));
    int i=0;
    while(i=0&&!vis[x][l])
        l--;
    while(rq;
    q.push(st);
    while(!q.empty())
    {
        st=q.front();
        q.pop();
        set_vis(st);
        if(st.flag==(1<<(n*2))-1)  //全部染色對的情況
        {
            printf(Case #%d: %d
,tt++,st.t);
            return ;
        }
        for(int i=0; i<2; i++)
        {
            for(int j=0; j>t;
    tt=1;
    while(t--)
    {
        cin>>n;
        cin>>ch[0]>>ch[1];
        memset(flag,0,sizeof(flag));
        st.flag=0;
        st.t=0;
        flag[0]=true ;
        bfs();
    }
    return 0;
}


 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved