首页 > 搜索 > DFS搜索 > HDU 3427-Clickomania-动态规划-[解题报告]HOJ
2014
03-23

HDU 3427-Clickomania-动态规划-[解题报告]HOJ

Clickomania

问题描述 :

Clickomania is a puzzle in which one starts with a rectangular grid of cells of different colours. In each step, a player selects ("clicks") a cell. All connected cells of the same colour as the selected cell (including itself) are removed if the selected cell is connected to at least one other cell of the same colour. The resulting "hole" is filled in by adjacent cells based on some rule, and the object of the game is to remove all cells in the grid. In this problem, we are interested in the one-dimensional version of the problem. The starting point of the puzzle is a string of colours (each represented by an uppercase letter).
At any point, one may select (click) a letter provided that the same letter occurs before or after the one selected. The substring of the same letter containing the selected letter is removed, and the string is shortened to remove the hole created. To solve the puzzle, the player has to remove all letters and obtain the empty string. If the player obtains a non-empty string in which no letter can be selected, then the player loses. For example, if one starts with the string "ABBAABBAAB", selecting the first "B" gives "AAABBAAB". Next, selecting the last "A" gives "AAABBB". Selecting an "A" followed by a "B" gives the empty string. On the other hand, if one selects the third "B" first, the string "ABBAAAAB" is obtained. One may verify that regardless of the next selections, we obtain either the string "A" or the string "B" in which no letter can be selected. Thus, one must be careful in the sequence of selections chosen in order to solve a puzzle. Furthermore,
there are some puzzles that cannot be solved regardless of the choice of selections. For example, "ABBAAAAB" is not a solvable puzzle. Some facts are known about solvable puzzles: The empty string is solvable. If x and y are solvable puzzles, so are xy, AxA, and AxAyA for any uppercase letter
A. All other puzzles not covered by the rules above are unsolvable.
Given a puzzle, your task is to determine whether it can be solved or not.

输入:

Each case of input is specified by a single line. Each line contains a string of uppercase letters. Each string has at least one but no more than 150 characters. The input is terminated by the end of file.

输出:

Each case of input is specified by a single line. Each line contains a string of uppercase letters. Each string has at least one but no more than 150 characters. The input is terminated by the end of file.

样例输入:

ABBAABBAAB
ABBAAAAB

样例输出:

solvable
unsolvable

题目链接:Clickomania

题目大意:Clickomannia是一款游戏,游戏规则是每次可以消除连续的同色方块,每次消除又会有新的连结,用字符串表示,问你能不能将整个字符串消除完。

算法分析:一道字符串题。我用dfs()过的。可以先将字符串缩减一下,将字符串中连续的部分用一个字符加一个数字来表示,用两个数组保存,加快扫描速度,从前往后扫描,每一个当前字符要么自成一串,构成合法序列,然后判断剩余字符串是否合法,要么和后面某一个相同字符合并,前提是他们中间的得是合法序列,按照这样分类方法直接dfs() + 标记。做这种类似的题,关键在于找到构成这些字符串的规则或叫词法,然后分类搜索+标记,应该能过。不过这题sha崽大牛结题报告说是区间DP,不懂,待看!

 

Clickomania代码

#include<stdio.h>
#include<string.h>
#define NN 155 
char str[NN];
int mark[NN][NN];
int num[NN];
char cha[NN];

int dfs(int l, int r)
{
    int i, t;
    if (l == r){   /*如果就剩一种字符,直接判断是相连的个数是否大于1*/
        if (num[l] > 1)
            return 1;
        else
            return 0;
    }
    if (mark[l][r]>= 0)
        return mark[l][r];
    /*当前字符和后面的任一个相同字符合并,前提是夹在他们中间的
    字符串是合法的 
    */ 
    char ch = cha[l];
    for (i = l + 1; i <= r; i++){
        if (cha[i] == ch){
            if (mark[l + 1][i - 1] = dfs(l + 1, i - 1)){
                t = mark[i][r];
                mark[i][r] = -1;
                num[i] += num[l];
                mark[i][r] = dfs(i, r);
                num[i] -= num[l];
                if (mark[i][r] == 1)
                {
                    mark[i][r] = t;
                    return 1;
                }
                mark[i][r] = t;
            }
        }
    }
    /*当前字符是合法的,直接判断后一部分是否合法
      即如果x,y都合法,则xy也合法 
    */
    if (num[l] > 1 && (mark[l + 1][r] = dfs(l + 1, r)))
        return 1;
    return 0;
}
int main()
{
    int len, time, index, i;
    while (scanf("%s", str) != EOF){
        len = strlen(str);
        if (len == 0){
            puts("solvable");
            continue;
        }
        
        /*将字符串缩减成两个数组,一个存出现过的字符,另一个存这个字符出现的次数
            例ABBBAACC        缩成ABAC 和 1322
        */
        time = 1;
        index = 0;
        for (i = 1; i <= len; i++){
            if (str[i] != str[i - 1]){
                cha[index] = str[i - 1];
                num[index] = time;
                time = 1;
                index++;
            }
            else
                time++;
        }    
        memset(mark, -1, sizeof(mark));
        if (dfs(0, index - 1))
            puts("solvable");
        else
            puts("unsolvable");
    }
    return 0;
}

 附带两组测试数据:

ABBCCBCAACCA

ABBBAACCDDBCCA

answer:

solvable

solvable

 

 

参考:http://www.cnblogs.com/ylfdrib/archive/2010/07/11/1775163.html