学习心得(code)

superlong@CoreCoder

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此处存放代码

常用链接

留言簿(4)

我参与的团队

搜索

  •  

最新随笔

最新评论

  • 1. re: Poj 1279
  • 对于一个凹多边形用叉积计算面积 后能根据结果的正负来判断给的点集的时针方向?
  • --bsshanghai
  • 2. re: Poj 3691
  • 你写的这个get_fail() 好像并是真正的get_fail,也是说fail指向的串并不是当前结点的子串。为什么要这样弄呢?
  • --acmer1183
  • 3. re: HDU2295[未登录]
  • 这个是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4. re: HDU2295
  • 评论内容较长,点击标题查看
  • --ylfdrib
  • 5. re: HOJ 11482
  • 呵呵..把代码发在这里很不错..以后我也试试...百度的编辑器太烂了....
  • --csuft1

阅读排行榜

评论排行榜


#include <stdio.h>
#include 
<ctime>
#include 
<stdlib.h>
#include 
<string.h>

const int SIZE = 16;
const int N = SIZE*SIZE*SIZE;
const int M = SIZE*SIZE*4;
const char LET = 'A';

char map[SIZE+1][SIZE+1];
int L[N*M+1], R[N*M+1], U[N*M+1], D[N*M+1], Sum[N*M+1];
int x[5], lenx;
int Row[N*M+1], Col[N*M+1];
int ans[N+1], anslen;
int id;
bool OK;

void pre() {
    
for(int i = 0; i <= M; i ++) {
        L[i] 
= i - 1;
        R[i] 
= i + 1;
        U[i] 
= D[i] = i;
        Sum[i] 
= 0;
    }
    L[
0= M; R[M] = 0;
    id 
= M + 1;
}

inline 
void insert(int i, int *xx) {
    
for(int j = 0; j < lenx; j ++, id ++) {
        
int x = xx[j]+1;
        Row[id] 
= i;
        Col[id] 
= x;
        Sum[x] 
++;
        U[id] 
= x;
        D[id] 
= D[x];
        U[D[x]] 
= id;
        D[x] 
= id;
        
if( j == 0 ) {
            L[id] 
= R[id] = id;
        } 
else {
            L[id] 
= id - 1;
            R[id] 
= id - j;
            R[id
-1= id;
            L[id
-j] = id;
        }
    }
}

void build() {
    
for(int i = 0; i < SIZE; i ++) {
        
for(int j = 0; j < SIZE; j ++) {
            
for(int k = 0; k < SIZE; k ++) {
                
int row = k+SIZE*j+SIZE*SIZE*i+1;
                lenx 
= 0;
                
if( map[i][j] == '-' || map[i][j] == k + 'A' ) {
                    x[lenx
++= SIZE*+ k;
                    x[lenx
++= SIZE*SIZE + SIZE*+ k;
                    
int temp = (i / 4* 4 + j / 4;
                    x[lenx
++= 2*SIZE*SIZE + temp * SIZE + k;
                    x[lenx
++= 3*SIZE*SIZE + i*SIZE + j;
                    insert(row, x);
                }
            }
        }
    }
}

inline 
void remove(int c) {
    R[L[c]] 
= R[c];
    L[R[c]] 
= L[c];
    
for(int id = D[c]; id != c; id = D[id]) {
        
for(int i = R[id]; i != id; i = R[i] ) {
            D[U[i]] 
= D[i];
            U[D[i]] 
= U[i];
            Sum[Col[i]] 
--;
        }
    }
}

inline 
void resume(int c) {
    L[R[c]] 
= c;
    R[L[c]] 
= c;
    
for(int id = D[c]; id != c; id = D[id]) {
        
for(int i = R[id]; i != id; i = R[i] ) {
            U[D[i]] 
= i;
            D[U[i]] 
= i;
            Sum[Col[i]] 
++;
        }
    }
}

bool dfs(int deep) {
    
if( R[0== 0 ) return true;
    
int column = R[0];
    
for(int i = R[0]; i != 0; i = R[i]) {
        
if( Sum[i] < Sum[column] ) {
            column 
= i;
            
if( Sum[column] < 2 ) break;
        }
    }
    remove(column);
    
for(int id = D[column]; id != column; id = D[id]) {
        ans[deep] 
= Row[id];
        
for(int i = R[id]; i != id; i = R[i]) remove(Col[i]);
        
if( dfs( deep + 1) ) return true;
        
for(int i = L[id]; i != id; i = L[i]) resume(Col[i]);
    }
    resume(column);
    
return false;
}


int main() {
    freopen(
"in.txt","r",stdin);
    
while( scanf("%s", map[0]) != EOF ) {
        
for(int i = 1; i < SIZE; i ++) scanf("%s", map[i]);
        pre();
        build();
        dfs(
0);
        
for(int i = 0; i < 256; i ++) {
            
int r = (ans[i] - 1/ SIZE / SIZE % SIZE;
            
int c = (ans[i] - 1/ SIZE % SIZE;
            
int val = (ans[i] - 1% SIZE;
            map[r][c] 
= val + 'A';
        }
        
for(int i = 0; i < SIZE; i ++){ 
            
for(int j = 0; j < SIZE; j ++) printf("%c",map[i][j]);
            printf(
"\n");
        }
        printf(
"\n");
    }
    
while(1);
}


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

posted on 2010-08-09 18:39 superlong 阅读(515) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理