第二题1175和一些思考

第二题本来是乱选一个题目是个求解同棋局问题，但是我觉得题意有点不清晰。（到底是形状匹配还是下法匹配），打开discuss，有人说数据有问题，很容易pass,另外一个人说和1175题目完全一样，我就去做了1175。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1175

1175是个很浪漫的题目，求解星空中所有相同的星簇（cluster）。 (98 IOI). 这个题目乍一看相当简单，但是做起来发现也是很容易出错的。
我的结果是16MS。未作更多优化。
思路很简单，先逐个查找出所有的星簇，当找到一个星星就从她开始递归的连接出所有的其他星星，存储宽，高等足够的信息。
然后从已经找到的星簇中寻找相同的，旋转和倒映的，如果没有找到就继续。找到了，要把星星标记重新标记为已经存在的那个字符。这里我对于旋转和映射没有使用公式而是使用一个scanner函数表，不同的方向各自一个，本质上就是对于源的一个scan顺序，目标只要使用scanner表离得任何一个通过检测就OK了。里面没用公式，推导公式我觉得不如组织好的代码更不容易出错。而且效率差不多。而且当时觉得scanner的状态可能对后面解题有帮助。（其实没有-_-!）

过了题目中的简单数据，提交上去，立刻WA...

（总是在拉屎的时候思路稍微清晰），如果两个相同的星系相互侵入，那么直接通过标记来判断就不对了，必须保留星星属于哪个星系的信息，否则再重标记之后就会导致以后的检测错误。简单了，再加个数组，存储星tag为他们所在星簇的idx.

OK。过了。
对于效率，因为数据量很小，并没有去做一些一优化，稍微加了一个星星总数判断，但是没有什么改观。
但是如果数据量很大，有一点值得思考，类似KMP的字符串普配算法，对于星系的匹配判断是可以做优化的：
就是一个方向的检测失败，这个结果是可以使用到其他方向的，而且这个因素是这个星簇自己的属性。因此可能有这么一个算法:

当方向d1测试失败，所处scanner的位置（简单起见，用其中一个整数，行）i,有：
此时i之前的数据都是已知的，那么就会有一些方向不需要再匹配，另外一些方向只需要从某个scanner位置开始匹配。这个信息可以作为:
f(d1, i, d2) =
{
   = -1 :不可能匹配
   or d2 scanner的起始位置 (i,j)。
}//d2是新的一个方向


那么每当得到一个cluster,就可以求出这个f的集合。可以自己和自己匹配得到。
比如：
[XXXXXX]
[XXXXXX]
[------]
[VVVVVV]
[VVVVVV]
x和v表示某两个方向的匹配成功，那么对x的来说，一次匹配失败如果在-----，那么到v的方向在匹配只需要到----
开始，如果在XXXXX就完蛋了，那么V也没必要比较。

这样做要增加空间复杂度来存储这些信息。降低星簇查找形同的匹配算法的时间复杂度常数因子。但是对于数据量很小，感觉得不偿失，自己和自己的匹配也是要时间的。这个想法也是一个粗糙的，没去实现，工作比较忙，也没什么时间

#include "stdio.h"

#define MAX_STAR 160
#define MAX_CLSTR 501
#define DIR_NUM 8
#define MAX_W   101
#define MAX_H   101

static char sky[MAX_H][MAX_W];
static int  tag[MAX_H][MAX_W];
static int w;
static int h;
   

typedef struct cluster_t
{
    /*int x[MAX_STAR];
    int y[MAX_STAR];*/
    int start_c;
    int start_l;
    int end_c;
    int end_l;

    int num;
   
    int  idx;
    char mark;
}TCluster;

typedef int (* _scanner_check_dir_fct)(TCluster * c1, TCluster * c2);
typedef int (* _scanner_step_dir_fct)(
    int *pi, int *pj, int sc, int ec, int sl, int el);

TCluster clusters[MAX_CLSTR];
int clusters_count = 0;

static int
simlar_check_star(
   TCluster * c1, int i1, int j1, TCluster *c2, int i2, int j2)
{
    return (      
                    (tag[i1][j1] == c1->idx && tag[i2][j2] == c2->idx)                  
               ||   (tag[i1][j1] != c1->idx && tag[i2][j2] != c2->idx)
              
           );
}




static int
_scanner_check_dir_wh(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == w2 && h1 == h2 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_check_dir_hw(TCluster * c1, TCluster * c2)
{
    int w1, h1, w2, h2;
    w1 = c1->end_c - c1->start_c + 1;
    w2 = c2->end_c - c2->start_c + 1;
    h1 = c1->end_l - c1->start_l + 1;
    h2 = c2->end_l - c2->start_l + 1;
    if(w1 == h2 && w2 == h1 && c1->num == c2->num)
    {
        return 1;
    }
    return 0;
}

static int
_scanner_step_dir_lrtb(int *pi, int *pj, int sc, int ec, int sl, int el)
{
   
    (*pj)++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_rltb(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj)--;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) ++;
        if(*pi > el)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_lrbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) ++;
    if(*pj > ec)
    {
        *pj = sc;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_rlbt(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pj) --;
    if(*pj < sc)
    {
        *pj = ec;
        (*pi) --;
        if(*pi < sl)
        {
            return 0;
        }
    }
    return 1;
}


static int
_scanner_step_dir_tblr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_btlr(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) ++;
        if(*pj > ec)
        {
            return 0;
        }
    }
    return 1;
}

static int
_scanner_step_dir_tbrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) ++;
    if(*pi > el)
    {
        *pi = sl;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



static int
_scanner_step_dir_btrl(int *pi, int *pj, int sc, int ec, int sl, int el)
{   
    (*pi) --;
    if(*pi < sl)
    {
        *pi = el;
        (*pj) --;
        if(*pj < sc)
        {
            return 0;
        }
    }
    return 1;
}



/*l:0, c:1*/
static int _scanner_start[DIR_NUM][2] = {
    {0, 0},
    {0, 1},
    {1, 0},
    {1, 1},
    {0, 0},
    {1, 0},
    {0, 1},
    {1, 1}};



static _scanner_step_dir_fct _scanner_step_funcs[DIR_NUM] = {
    _scanner_step_dir_lrtb,
    _scanner_step_dir_rltb,
    _scanner_step_dir_lrbt,
    _scanner_step_dir_rlbt,
    _scanner_step_dir_tblr,
    _scanner_step_dir_btlr,   
    _scanner_step_dir_tbrl,
    _scanner_step_dir_btrl
};

static _scanner_check_dir_fct  _scanner_filter_funcs[DIR_NUM] = {
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_wh,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw,
    _scanner_check_dir_hw
};


static int
is_same(TCluster * c1, TCluster * c2, int * pdir)
{
    int dir;
    int i1, j1;
    int i2, j2;

  

    for(dir = 0;  dir < DIR_NUM; dir ++)
    {
        if(_scanner_filter_funcs[dir](
            c1, c2) == 0)
        {
            continue;
        }
        i2 = (_scanner_start[dir][0] == 1)?(c2->end_l):(c2->start_l);
        j2 = (_scanner_start[dir][1] == 1)?(c2->end_c):(c2->start_c);

        for(i1 = c1->start_l; i1 <= c1->end_l; i1 ++)
        {  
            for(j1 = c1->start_c; j1 <= c1->end_c; j1 ++)
            {              
                if(simlar_check_star(c1, i1, j1, c2, i2, j2))
                {
                    _scanner_step_funcs[dir](
                        &i2,
                        &j2,
                        c2->start_c,
                        c2->end_c,
                        c2->start_l,
                        c2->end_l);
                    continue;
                }
                else
                {
                    goto LB_NextCheck;
                }
              
            }           
        }
        *pdir = dir;
        return 1;
LB_NextCheck:;
    }

    return 0;
}


static void
remark_as_old(TCluster * clstr, int curmark, int oldmark)
{
    int i;
    int j;
    for(i = clstr->start_l; i <= clstr->end_l; i ++)
    {
        for(j = clstr->start_c; j <= clstr->end_c; j ++)
        {           
            if(sky[i][j] == curmark && tag[i][j] == clstr->idx)
            {
                sky[i][j] = oldmark;
            }
        }
    }
    clstr->mark = oldmark;
   
}

static int
find_and_merge_cluster(int c_idx)
{
    int i;
    int dir;
    TCluster * clstr;
    TCluster * old_clstr;

    clstr = clusters + c_idx;
   
    for(i = 0; i < c_idx; i ++)
    {
        old_clstr = clusters + i;
        if(is_same(old_clstr, clstr,  &dir) == 1)
        {
            remark_as_old(clstr, clstr->mark, old_clstr->mark);
            return 1;  
        }
    }
    return 0;
}


static void
build_cluster(int c_idx, int i, int j, char cur_mark)
{
    if(i <>= h || j >= w)
    {
        return;
    }

    if(sky[i][j] == '1')
    {
        sky[i][j] = cur_mark;
        tag[i][j] = c_idx;
        clusters[c_idx].num ++;
      
        if(i < clusters[c_idx].start_l)
        {
            clusters[c_idx].start_l = i;           
        }
        if(j < clusters[c_idx].start_c)
        {
            clusters[c_idx].start_c = j;           
        }
        if(i > clusters[c_idx].end_l)
        {
            clusters[c_idx].end_l = i;           
        }
        if(j > clusters[c_idx].end_c)
        {
            clusters[c_idx].end_c = j;           
        }
     
    }
    else
    {
        return;
    }

    build_cluster(c_idx, i - 1, j - 1, cur_mark);
    build_cluster(c_idx, i    , j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j - 1, cur_mark);
    build_cluster(c_idx, i + 1, j    , cur_mark);
    build_cluster(c_idx, i + 1, j + 1, cur_mark);
    build_cluster(c_idx, i    , j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j + 1, cur_mark);
    build_cluster(c_idx, i - 1, j    , cur_mark);
}




static void
get_clusters()
{
    int i, j;
    int idx;
    char cur_mark = 'a';
   
    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            if(sky[i][j] == '1')
            {
                idx = clusters_count;

                clusters[idx].mark      = cur_mark;
                clusters[idx].start_c   = MAX_W + 1;
                clusters[idx].end_c     = -1;
                clusters[idx].start_l   = MAX_H + 1;
                clusters[idx].end_l     = -1;
                clusters[idx].idx       = idx;
               
                build_cluster(idx, i, j, cur_mark);
                /*Not found old the same*/
                if(find_and_merge_cluster(idx) == 0)
                {
                    cur_mark ++;
                }

                clusters_count ++;
            }
        }
    }
}

static void
output()
{
    int i;
    int j;

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            printf("%c", sky[i][j]);
        }
        printf("\n");
    }

}

int p_1175_go()
{
    int i;
    int j; 
    char inp;

    scanf("%d\n", &w);
    scanf("%d\n", &h);

    for(i = 0; i < h; i ++)
    {
        for(j = 0; j < w; j ++)
        {
            scanf("%c", &inp);           
            sky[i][j] = inp; 
            tag[i][j] = -1;
        }
        scanf("%c", &inp);
    }
   
    get_clusters();
    output();    
}
int main(void)
{
   
    p_1175_go(1175);
}

BT的第一题

做ACM题计划刚开始就让自己撞了个大钉子，随便选了一个题目，1011，没想到是个超级BT的搜索剪枝题。
Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output

The output should contains the smallest possible length of original sticks, one per line.
Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output

6
5刚看到这个题目觉得还挺简单的，（其实主要原因是有个中文翻译-_-~~). 大概思路就是一开始根据题目的条件有范围确定，接着就是可以回朔搜索了。搜索的时候要剪枝。。.
但是做了就知道根本不是这么简单的。TLE了无数次。
问题的特点就是除了快速求满足一个长度棍子的解之外，还得快速去掉解。
第一个很容易想到的，求解范围，需要整除棍子长度之和，不能小于最大的小棍子长度，个数在小棍子数之内。这些想不到，这题目直接88.
然后搜索的策略，我一开始就走的不对，一开始的方案是让小棍子选择原始棍子的标号搜索，然后剪去原始棍子标号重复。但是这个办法剪枝太难了，因为很容易进入很深的搜索却还对局势没有掌握。放弃。
只能一根根根子去求解，这里面剪枝就多了，棍子排序（自然会想到排序的，快点从大棍子的失败中解脱，并且在后面是的搜索本身呈现顺序性，易于剪枝），然后就是单独原始棍子的后续不要重复的剪枝，还有一个同一长度不在再次使用（在前面排了序，这儿就方便了）的剪枝。有些明显的东西比如长度要刚好满足一个棍子不能叫做剪枝了。上传TLE. TLE. TLE .......
上班比较忙，周末回家才想了一些新办法，但是不知道有些剪枝是不是有问题，最后找到几个可能的剪枝，但是实现起来，代码看着越来越烦了，真不想做了，后来才发现代码里有个保守的错误，这个错误改掉。AC.....大概600MS,虽然不是0MS，我也满意了，痛苦啊。。虽然还有可剪的，但是我已经不想再折磨自己了。
后来才知道1011是个经典的，BT的搜索剪枝题目。
BS 自己。

PS.那个排序用C qsort，速度比泡泡慢 -_~
代码改了很多，看着有点想吐！
#include "stdio.h"

int inp_b[64];
int inp_c = 0;
int min_inp;
int max_inp;
int curL[64];
int curCount[64];

/*int dbg_lay[64][5];*/
int lay[64][64];
int maxC;
int minL;

int used[64];
int usedCount = 0;
static int curSrcIdx;

#define USE(idx)\
do{\
used[idx] = 1;\
curL[curSrcIdx] += inp_b[idx];\
curCount[curSrcIdx] ++;\
usedCount ++;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx] - 1] = inp_b[idx];*/\
lay[curSrcIdx][curCount[curSrcIdx] - 1] = idx;\
}while(0)
#define UNUSE(idx)\
do{\
curL[curSrcIdx] -= inp_b[idx];\
used[idx] = 0; \
curCount[curSrcIdx] --;\
usedCount--;\
/*dbg_lay[curSrcIdx][curCount[curSrcIdx]] = 0;*/\
lay[curSrcIdx][curCount[curSrcIdx]] = 0;\
}while(0)

static int tryloop2(int lastIdx)
{
int idx;
int last = 100000;
int ret;
  
if(inp_c - usedCount < idx =" lastIdx;" last =" inp_b[idx];" cursrcidx ="="" ret =" tryloop2(lay[curSrcIdx" cursrcidx ="="" ret ="="" ret ="tryloop2(idx))" ret ="="" i =" 0;" i =" 0;" usedcount =" 0;" cursrcidx =" 0;"> *((int *)p2) )
{
 return -1;
}
else if(*((int *)p1) < *((int *)p2))  {   return 1;  }  else   {   return 0;  } } void b_sort(int inp_b[], int inp_c) {  int i;  int j;  int t;  for(i = inp_c - 1; i >= 0 ; i --)
{
 for(j = 0; j <> inp_b[j])
  {
   t = inp_b[j + 1];
   inp_b[j + 1] = inp_b[j];
   inp_b[j] = t;
  }
 }
}
}
int main(void)
{

int i;


int s = 0;


while(1)
{
 scanf("%d", &inp_c);
 if(inp_c == 0)
 {
  return 0;
 }

 for(i = 0; i < s =" 0;" max_inp =" 0;" min_inp =" 100;" i =" 0;"> inp_b[i])
  {
   min_inp = inp_b[i];
  }
  if(max_inp < max_inp =" inp_b[i];" maxc =" inp_c;"> 0; maxC --)
 {
 
  if(s % maxC == 0)
  {
   minL = s/maxC;
   if(minL < max_inp)
   {
    continue;
   }
  
   //An possible minL;
   if(start_tryloop() == 1)
   {
    break;
   }
  }
 }
}
}

在Linux下面开发GL

自从开始用DFB重新实现GL,但是终于要到目标平台上面做Porting,效果很差，问题很多。这段时间都很忙。看得很紧，今天终于出来界面了，但是问题太多了。Linux和以前的嵌入式的OS差距太大了。首先问题就是地址，以前的地址都是没有用户空间和内核空间的区别，现在有了，问题就出来了，关键是以前留下的代码很难更改。加上要实现的接口是一个用了好几年的一个庞大的库，自我有对下面Driver的依赖，转接到DFB上面也是相当的麻烦的扭捏。 这段时间到时真的学了一点点Linux开发，不过到现在Linux命令还不熟，真倒。