首页 > ACM题库 > HDU-杭电 > HDU 1332 LC-Display-DFS-[解题报告] C++
2013
12-09

HDU 1332 LC-Display-DFS-[解题报告] C++

LC-Display

问题描述 :

A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

输入:

The input contains several lines, one for each number to be displayed. Each line contains two integers s, n (1 <= s <= 10, 0 <= n <= 99 999 999), where n is the number to be displayed and s is the size in which it shall be displayed.

The input file will be terminated by a line containing two zeros. This line should not be processed.

输出:

Output the numbers given in the input file in an LC-display-style using s “-” signs for the horizontal segments and s “|” signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.

Output a blank line after each number. (You will find a sample of each digit in the sample output.)

样例输入:

2 12345
3 67890
0 0

样例输出:

      --   --        -- 
   |    |    | |  | | 
   |    |    | |  | | 
      --   --   --   -- 
   | |       |    |    |
   | |       |    |    |
      --   --        -- 

 ---   ---   ---   ---   --- 
|         | |   | |   | |   |
|         | |   | |   | |   |
|         | |   | |   | |   |
 ---         ---   --- 
|   |     | |   |     | |   |
|   |     | |   |     | |   |
|   |     | |   |     | |   |
 ---         ---   ---   ---

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct Eight
{
    char matrix[3][3];
    int x,y;
};
Eight src,dst;
int step[][2]= {{0,1},{-1,0},{1,0},{0,-1}};
int dep,nextstep;
char * cmd="dlru",ans[100];
bool flag;
bool OK(const Eight& src)
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(src.matrix[i][j] && src.matrix[i][j] !=i*3+j+1)
                return false;
    return true;
}
int h(const Eight& src)
{
    int ans =0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(src.matrix[i][j])
                ans += abs(i-(src.matrix[i][j]-1)/3)+abs(j-(src.matrix[i][j]-1)%3);
    return ans;
}
bool CanSovle()
{
    int ans = 0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(src.matrix[i][j])
                for(int y=0;y<3;y++)
                    for(int x=0;y*3+x<=i*3+j && x<3;x++)
                        if(src.matrix[y][x] && src.matrix[y][x] >src.matrix[i][j])
                            ans++;
    return ans % 2 ==0;
}
void dfs(int x,Eight src,int from)
{
    if(OK(src))
    {
        flag = true;
        return;
    }
    int t = h(src);
    if(x + t >dep || flag)
    {
        nextstep = min (nextstep,x+t);
        return;
    }
    for(int i=0; i<4 && !flag; i++)
    {
        if(from + i ==3)
            continue;
        int tx = src.x + step[i][0];
        int ty = src.y + step[i][1];
        if(tx >=0 && tx<=2 && ty>=0 && ty<=2)
        {
            Eight tmp = src;
            swap(tmp.matrix[src.y][src.x],tmp.matrix[ty][tx]);
            tmp.x = tx;
            tmp.y = ty;
            dfs(x+1,tmp,i);
            if(flag)
                ans[x]=cmd[i];
        }
    }
}
void IDAstar(Eight src)
{
    memset(ans,0,sizeof(ans));
    for(dep = h(src);!flag; dep=nextstep)
    {
        nextstep=100;
        dfs(0,src,-1);
    }
}
int main()
{
    while(1)
    {
        flag = false;
        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                if(scanf(" %c",&src.matrix[i][j])!=1)
                    return 0;
                if(src.matrix[i][j]=='x')
                {
                    src.matrix[i][j]=0;
                    src.y=i;
                    src.x=j;
                }
                else
                    src.matrix[i][j]-='0';
            }
        }
        if(CanSovle())
        {
            IDAstar(src);
            printf("%s\n",ans);
        }
        else
            printf("unsolvable\n");
    }
    return 0;
}

解题报告转自:http://www.cnblogs.com/luyi0619/archive/2010/10/29/1864808.html


,
  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.