学习心得(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 <iostream>
#include 
<string>
#include 
<queue>
#include 
<map>
using namespace std;

char change[][10= {"413526789""253146789""152463789""136425789"
                     
"123746859""123586479""123485796""123469758"};
char end[11];
string sta;
int num;
bool flag = 0;

queue 
< string > q[2]; // 0 -> zheng  1-> fan
map <string , bool> h[2];

void expend(int type, string ini)
{
    
char next[10];
    
forint i= 0; i< 8; i ++ )
    {
        
forint j= 0; j< 9; j ++ )
            next[j]
= ini[ change[i][j]- '0'- 1 ];
        next[
9]= 0;
        
if( h[type][next] ) continue;
        
if( h[1-type][next] ) 
        {
            flag 
= 1;
            
return;
        }
        q[type].push(next);
        h[type][next] 
= 1;
    }
}

int bfs()
{
    
int cnt = 0, index, len;
    
while!q[0].empty() ) q[0].pop();
    
while!q[1].empty() ) q[1].pop();
    h[
0].clear();    h[1].clear();
    sta 
= "123456789";
    h[
0][sta] = 1;
    h[
1][end] = 1;
    
if(h[0][end]) return 0;
    q[
0].push(sta);
    q[
1].push(end);
    flag 
= 0;
    
string temp;
    
while!q[0].empty() || !q[1].empty() )
    {
        index 
= 0;
        
if( q[0].size() > q[1].size() ) index = 1;
        
if( q[index].size() == 0 ) index = 1 - index;
        len 
= q[index].size();    
        
while(len --)
        {
            temp 
= q[index].front();
            q[index].pop();
            expend(index, temp);
            
if(flag) break;
        }
        cnt 
++;
        
if(flag) return cnt;
        
if(cnt > num) return -1;
    }
}


int main()
{
    
int test = 0;
    
while(gets(end) != NULL)
    {
        
if!strcmp(end, "0000000000") ) break;
        num 
= end[0- '0';
        
for(int i = 0; i <= 9; i ++) end[i] = end[i + 1];
        
int ans = bfs();
        
if(ans < 0 || (ans >0 && num < ans) ) ans = -1;
        printf(
"%d. %d\n"++test, ans);
    }
}

如果使用逆序判重的话当然会跑得更快
#include <iostream>
#include 
<string>
#include 
<queue>
using namespace std;

char change[][10= {"413526789""253146789""152463789""136425789"
                     
"123746859""123586479""123485796""123469758"};
char end[11];
string sta;
int num;
bool flag = 0;

queue 
< string > q[2]; // 0 -> zheng  1-> fan
bool h[2][370000];

int map(string ss)
{
    
int hash = 0base = 1, answer = 0;
    
for(int i = 0; i < 9; i ++)
    {
        
if(!basebase = 1;
        
base *= i; hash = 0;
        
for(int j = 0; j < i; j ++)
        
if(ss[j] > ss[i]) hash ++;
        answer 
+= hash * base;
    }
    
return answer;
}

void expend(int type, string ini)
{
    
char next[10];
    
int tmp;
    
forint i= 0; i< 8; i ++ )
    {
        
forint j= 0; j< 9; j ++ )
            next[j]
= ini[ change[i][j]- '0'- 1 ];
        next[
9]= 0;
        tmp 
= map(next);
        
if( h[type][tmp] ) continue;
        
if( h[1-type][tmp] ) 
        {
            flag 
= 1;
            
return;
        }
        q[type].push(next);
        h[type][tmp] 
= 1;
    }
}

int bfs()
{
    
int cnt = 0, index, len;
    
while!q[0].empty() ) q[0].pop();
    
while!q[1].empty() ) q[1].pop();
    memset(h, 
0sizeof(h));
    sta 
= "123456789";
    h[
0][map(sta)] = 1;
    h[
1][map(end)] = 1;
    
if(h[0][map(end)]) return 0;
    q[
0].push(sta);
    q[
1].push(end);
    flag 
= 0;
    
string temp;
    
while!q[0].empty() || !q[1].empty() )
    {
        index 
= 0;
        
if( q[0].size() > q[1].size() ) index = 1;
        
if( q[index].size() == 0 ) index = 1 - index;
        len 
= q[index].size();    
        
while(len --)
        {
            temp 
= q[index].front();
            q[index].pop();
            expend(index, temp);
            
if(flag) break;
        }
        cnt 
++;
        
if(flag) return cnt;
        
if(cnt > num) return -1;
    }
}

int main()
{
    
int test = 0;
    
while(gets(end) != NULL)
    {
        
if!strcmp(end, "0000000000") ) break;
        num 
= end[0- '0';
        
for(int i = 0; i <= 9; i ++) end[i] = end[i + 1];
        
int ans = bfs();
        
if(ans < 0 || (ans >0 && num < ans) ) ans = -1;
        printf(
"%d. %d\n"++test, ans);
    }
}

posted on 2009-08-21 20:34 superlong 阅读(129) 评论(0)  编辑 收藏 引用

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