第二题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);
}