学习心得(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 
<stdlib.h>
#include 
<string.h>

int  num[9], ini;
int  L;
bool flag;
int  mv[4= {13-1-3};//right down left up
int  path[1001];
int  len;
char map[4= {'r''d''l''u'};

void read()
{
    
char s[2];
    
for(int i = 0; i < 9; i ++)
    {
        scanf(
"%s", s);
        
if(s[0== 'x') {num[i] = 0; ini = i;}
        
else            num[i] = s[0- '0';
    }
}

bool ok()   // jud for destination
{
    
for(int i = 0; i < 8; i ++)
        
if(num[i] != i + 1return false;
    
return true;
}

bool jud(int pos, int i)  //jud for right
{
    
if(pos % 3 != 2 && i == 0return true;
    
if(pos < 6 && i == 1return true;
    
if(pos % 3 != 0 && i == 2return true;
    
if(pos > 2 && i == 3return true;
    
return false;
}

int cal()
{
    
int cost = 0;
    
for(int i = 0; i < 9; i ++)
    
if(num[i])
        cost 
+= abs((num[i] - 1)%3 - i%3+ abs((num[i] - 1)/3 - i/3);
    
return cost;
}

void dfs(int pos, int deep)
{
    
int i, J, cost;
    
if(deep == L)
    {
        
if(ok()) flag = true;
        
return;
    }
    
for(i = 0; i < 4; i ++)
    {
        
if(!jud(pos, i)) continue;
        num[pos] 
^= num[pos + mv[i]] ^= num[pos] ^= num[pos + mv[i]];//state change
        
        cost 
= cal();
        
if(cost + deep  < L)
        {
            path[len
++= i;
            dfs(pos 
+ mv[i], deep + 1);
            
if(flag) return;
            len 
--;
        }
        num[pos] 
^= num[pos + mv[i]] ^= num[pos] ^= num[pos + mv[i]];//state again
    }    
}

void out()
{
    
int i;
    
//printf("%d\n",len);
    for(i = 0; i < len; i ++)
        printf(
"%c", map[path[i]]);
    puts(
"");
}

int main()
{
    read();
    L 
= 1; len = 0;
    flag 
= false;
    
while(!flag)
    {
        dfs(ini, 
0);
        L 
++;
    }
    
out();
}

posted on 2009-09-03 01:19 superlong 阅读(134) 评论(0)  编辑 收藏 引用

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