Java教程

[NOIP2013 提高组] 华容道

本文主要是介绍[NOIP2013 提高组] 华容道,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这道题记录状态的思想挺好的

假如棋子在(i,j):

那么它上面空格的编号为((i-1)*4+(j-1)*4+0)

那么它下面空格的编号为((i-1)*4+(j-1)*4+1)

那么它左面空格的编号为((i-1)*4+(j-1)*4+2)

那么它右面空格的编号为((i-1)*4+(j-1)*4+3)


 

↑手动分割

所以俺们要记录的

①在不动棋子本身的情况下,棋子周围空格乱转的最小步数(在可行情况下)

//伪代码
(x,y)棋子位置
for i from 0 to 3
    for j from i+1 to 3
        int step=bfs((x-1)*4+(y-1)*4+i,(x-1)*4+(y-1)*4+j);
       add((x-1)*4+(y-1)*4+i,(x-1)*4+(y-1)*4+j,step);
       add((x-1)*4+(y-1)*4+j,(x-1)*4+(y-1)*4+i,step);    

②移动棋子(分为左右移动与上下运动)(在可行情况下)

//伪代码
(x,y)棋子位置
add((x-1)*4+(y-1)*4+1,x*4+(y-1)*4+0,1);//上到下 
add((x-1)*4+(y-1)*4+0,(x-2)*4+(y-1)*4+1,1);//下到上
add((x-1)*4+(y-1)*4+3,(x-1)*4+y*4+2,1);//左到右 
add((x-1)*4+(y-1)*4+2,(x-1)*4+(y-2)*4+3,1);//右到左 

求路径步骤:将空格移到起始棋子的上下左右的步数+开始最短路+在结束棋子上下左右空格中寻找答案

END

没打代码,嘿嘿(again)

 

这篇关于[NOIP2013 提高组] 华容道的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!