import java.awt.*
import java.awt.event.*
//主函数
public class Main {
public static void main(String[] args) {
new Hua_Rong_Road()
}
}
//人物按钮颜色
class Person extends Button implements FocusListener{
int number
Color c=new Color(255,245,170)
Person(int number,String s)
{
super(s)
setBackground(c)/汪李/人物的颜色背景是黄色
this.number=number
c=getBackground()
addFocusListener(this)//好像是焦点监听器
}
public void focusGained(FocusEvent e)
{
setBackground(Color.red)//只要单击该按钮则按钮变颜色
}
public void focusLost(FocusEvent e) {
setBackground(c)//上一个按钮回复原先的颜色困物迟
}
}
//华容道总类
class Hua_Rong_Road extends Frame implements MouseListener,KeyListener,ActionListener{
Person person[] = new Person[10]
Button left,right,above,below
Button restart = new Button("Start")//重新开始按钮
public Hua_Rong_Road()
{
init()
setBounds(100,100,320,360)
setVisible(true)//设置Frame为可见，默认为不可见
validate()
addWindowListener(
new WindowAdapter()
{
public void windowClosing(WindowEvent e)
{
System.exit(0)
}
}
)
}
public void init()
{
setLayout(null)
add(restart)
restart.setBounds(100, 320, 120, 25)
restart.addActionListener(this)
String name[]={"我","陆逊","姜维","陈宫"蚂薯,"许攸","邓艾","周瑜","庞统","诸葛亮","贾诩"}
for(int k=0k<name.lengthk++)
{
person[k]=new Person(k,name[k])
person[k].addMouseListener(this)
person[k].addKeyListener(this)
add(person[k])
}//为所有的按钮注册所需的东西
person[0].setBounds(104, 54, 100, 100)
person[1].setBounds(104,154, 100, 50)
person[2].setBounds(54, 154, 50, 100)
person[3].setBounds(204, 154, 50, 100)
person[4].setBounds(54, 54, 50, 100)
person[5].setBounds(204, 54, 50, 100)
person[6].setBounds(54, 254,50, 50)
person[7].setBounds(204, 254, 50, 50)
person[8].setBounds(104, 204, 50, 50)
person[9].setBounds(154, 204, 50, 50)
//初始化按钮的位子
person[0].requestFocus()
left=new Button()
right=new Button()
above=new Button()
below=new Button()
left.setBounds(49,49,5,260)
right.setBounds(254,49,5,260)
above.setBounds(49,49,210,5)
below.setBounds(49,304,210,5)
validate()
}
public void keyTyped(KeyEvent e){}
public void keyReleased(KeyEvent e){}
public void keyPressed(KeyEvent e)
{
Person man=(Person)e.getSource()
if(e.getKeyCode()==KeyEvent.VK_DOWN)
{
go(man,below)
}
if(e.getKeyCode()==KeyEvent.VK_UP)
{
go(man,above)
}
if(e.getKeyCode()==KeyEvent.VK_LEFT)
{
go(man,left)
}
if(e.getKeyCode()==KeyEvent.VK_RIGHT)
{
go(man,right)
}
}
public void mousePressed(MouseEvent e)
{
Person man =(Person)e.getSource()
int x=-1,y=-1
x=e.getX()
y=e.getY()
int w=man.getBounds().width
int h=man.getBounds().height
if(y>h/2)
{
go(man,below)
}
if(y<h/2)
{
go(man,above)
}
if(x<w/2)
{
go(man,left)
}
if(x>w/2)
{
go(man,right)
}
}
public void mouseReleased(MouseEvent e){}
public void mouseEntered(MouseEvent e){}
public void mouseExited(MouseEvent e){}
public void mouseClicked(MouseEvent e){}
public void go(Person man,Button direction)
{
boolean move=true
Rectangle manRect=man.getBounds()
int x=man.getBounds().x
int y=man.getBounds().y
if(direction==below)
y=y+50
else if(direction==above)
y=y-50
else if(direction==left)
x=x-50
else if(direction==right)
x=x+50
manRect.setLocation(x,y)
Rectangle directionRect=direction.getBounds()
for(int k=0k<10k++)
{
Rectangle personRect=person[k].getBounds()
if((manRect.intersects(personRect))&&(man.number!=k))
{
move=false
}
}
if(manRect.intersects(directionRect))
{
move=false
}
if(move==true)
{
man.setLocation(x,y)
}
}
public void actionPerformed(ActionEvent e)
{
dispose()
new Hua_Rong_Road()
}
}
华容道问题用计算机求解，一般采用广度搜索的方法，其原理很简单，就是把下一步可能有的走法全部算出来，比如第一步有五种走法，将这五种走法的下一步走法分别算出来，可能会有三十步，在继续将这三十步走法的下一步走法分别算出来，可能会更多，以此类推，直到达到目标状态（曹 *** 在出口位置）为止。在解华容道的问题上，我觉得有两个问题比较棘手。
其一、算法的效率。
其二、获得最优解法。
我是这样解决的：
1、 要提高算法的效率，首先要知道算法的瓶颈在什么地方，蔽森在得出每一个状态（走完一步各个棋子的位置）都要和前面的状态进行比较，以保证不重复，随着步数的增多，状态数会大幅度增加，这是，和前面的状态比较这一过程成了整个算法的效率。解决的办法，从两个地方着手，其一，增加每一步比较的速度。在程序中，用5*4的数组表示一个状态，这样，每一次比较要比较二十个数，因为数组中每个数定义从0-7，用三个二进制位可以表示，3*20=60位，用一个64位数就可以表示（有的资料说用四个字节就可以，我实在想不出来），这样每次比较一个64位数就可以了。其二、减少比较的状态，这是提高效率的关键。比较的时候不要和前面所有的状态都进行比较，只要和前两步的所有状态进行比较就可以了。经过以上的优化，在解横刀立马时，大约需要一，两秒钟就可以了，（我的机器，赛扬1.1OC1.46）。
2、 获得最优解法，比如横刀立马是81步，这里的一步指移动一个棋子，可以把一个卒子向一个方向移动两格，或基带者卒子拐弯移动两格，或者一搏并芦个将向一个方向移动两格（横将横着移，竖将竖着移）都是一步。获得最优解法的关键是把下一步可能有的走法全部算出来，不能遗漏。我是根据空格来算走法的的，分三种情况：
① 、卒子拐弯移动，如果有连着两个空格（横向的），则如果在它的上面或下面（有四个位置）有卒子的话，那么可以拐弯移动，有四种走法。如果两个空格是竖向的，那么，空格的左右如果有卒子，也可以拐弯移动，也有四种走法。
②、向一个方向移动两格，这里可能出现的情况有：卒子向一个方向移动两格，横将横着移两格，竖将竖着移两格
③、考虑向一个方向移动一格的情况，这里情况很多，我不一一列举了。
以上的算法很麻烦，很大一部分程序用来写这个了，如果大家有更简单的，可以告诉我，但一个原则，必须把所有的走法全部考虑。
另外，说一下我在写程序时的小插曲。程序快写好时，运行时发现，每解一次，内存使用会增加7，8兆，后来发现分配的内存每释放导致的，其实在函数中也就分配了几十个字节，由于被重复调用，最后泄漏的内存就很可观了，以后使用指针分配内存可要注意了,（C用malloc，C++用new），一定要释放，弄不好，^@^。
程序用dev-C++ 4.9.9.0（可以从网上下，只有十多兆）编译通过，因为dev C++没有框架等东西，所以界面直接用window API写的。生成的可执行文件很小，68 K。另外，在程序中可以自定义布局，用5*4数表示。其中0-空格，1-卒子，2到6 将，7曹 *** 。
最后附上所有的源代码。
main.cpp程序为：
#include <string>
#include <windows.h>
#include "HRD_Calculate.h"
char str[80]
PAINTSTRUCT pa
HDC hdc,memdc
RECT rect
HBITMAP hbit
HBRUSH hbrush
HPEN hpen
POINT point
hrd_calculate hrd// User declarations
int current_step
unsigned __int8 display_node[5][4]
/* Declare Windows procedure */
LRESULT CALLBACK WindowProcedure (HWND, UINT, WPARAM, LPARAM)
/* Make the class name into a global variable */
char szClassName[ ] = "WindowsApp"
int WINAPI WinMain (HINSTANCE hThisInstance,
HINSTANCE hPrevInstance,
LPSTR lpszArgument,
int nFunsterStil)
{
HWND hwnd /* This is the handle for our window */
MSG messages /* Here messages to the application are saved */
WNDCLASSEX wincl /* Data structure for the windowclass */
/* The Window structure */
wincl.hInstance = hThisInstance
wincl.lpszClassName = szClassName
wincl.lpfnWndProc = WindowProcedure /* This function is called by windows */
wincl.style = CS_DBLCLKS/* Catch double-clicks */
wincl.cbSize = sizeof (WNDCLASSEX)
/* Use default icon and mouse-pointer */
wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION)
wincl.hIconSm = LoadIcon (NULL, IDI_WINLOGO)
wincl.hCursor = LoadCursor (NULL, IDC_ARROW)
wincl.lpszMenuName = NULL/* No menu */
wincl.cbClsExtra = 0 /* No extra bytes after the window class */
wincl.cbWndExtra = 0 /* structure or the window instance */
/* Use Windows's default color as the background of the window */
wincl.hbrBackground = (HBRUSH) COLOR_BTNFACE
/* Register the window class, and if it fails quit the program */
if (!RegisterClassEx (&wincl))
return 0
/* The class is registered, let's create the program*/
hwnd = CreateWindowEx (
0, /* Extended possibilites for variation */
szClassName, /* Classname */
"华容道", /* Title Text */
WS_OVERLAPPED|WS_CAPTION|WS_SYSMENU, /* default window */
CW_USEDEFAULT, /* Windows decides the position */
CW_USEDEFAULT, /* where the window ends up on the screen */
544, /* The programs width */
375, /* and height in pixels */
HWND_DESKTOP,/* The window is a child-window to desktop */
NULL,/* No menu */
hThisInstance, /* Program Instance handler */
NULL /* No Window Creation data */
)
/* Make the window visible on the screen */
ShowWindow (hwnd, nFunsterStil)
/* Run the message loop. It will run until GetMessage() returns 0 */
while (GetMessage (&messages, NULL, 0, 0))
{
/* Translate virtual-key messages into character messages */
TranslateMessage(&messages)
/* Send message to WindowProcedure */
DispatchMessage(&messages)
}
/* The program return-value is 0 - The value that PostQuitMessage() gave */
return messages.wParam
}
/* This function is called by the Windows function DispatchMessage() */
LRESULT CALLBACK WindowProcedure (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int initx=20,inity=20,grid=50,interspace=3,arc=25
int i,j,m=0
char s[100]
switch (message) /* handle the messages */
{
case WM_CREATE:
{
CreateWindow("BUTTON","解题",WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,350,150,100,
30,hwnd,(HMENU)1000,((LPCREATESTRUCT) lParam)->hInstance,NULL)
CreateWindow("BUTTON","自定义布局",WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,350,90,100,
30,hwnd,(HMENU)1001,((LPCREATESTRUCT) lParam)->hInstance,NULL)
CreateWindow("EDIT","27732773144115510660",WS_CHILD|WS_VISIBLE|ES_NUMBER|WS_BORDER,350,50,165,
20,hwnd,(HMENU)1002,((LPCREATESTRUCT) lParam)->hInstance,NULL)
GetClientRect(hwnd,&rect)
hdc=GetDC(hwnd)
memdc=CreateCompatibleDC(hdc)
hbit=CreateCompatibleBitmap(hdc,rect.right,rect.bottom)
SelectObject(memdc,hbit)
hbrush = (HBRUSH) GetStockObject(WHITE_BRUSH)
SelectObject(memdc, hbrush)
//hpen = (HPEN) GetStockObject(BLACK_PEN)
//SelectObject(memdc, hpen)
ReleaseDC(hwnd,hdc)
///////////////////////////////////////
display_node[0][0]=GENERAL1
display_node[0][1]=CAOCAO
display_node[0][2]=CAOCAO
display_node[0][3]=GENERAL2
display_node[1][0]=GENERAL1
display_node[1][1]=CAOCAO
display_node[1][2]=CAOCAO
display_node[1][3]=GENERAL2
display_node[2][0]=GENERAL3
display_node[2][1]=GENERAL5
display_node[2][2]=GENERAL5
display_node[2][3]=GENERAL4
display_node[3][0]=GENERAL3
display_node[3][1]=SOLDIER
display_node[3][2]=SOLDIER
display_node[3][3]=GENERAL4
display_node[4][0]=SOLDIER
display_node[4][1]=BLANK
display_node[4][2]=BLANK
display_node[4][3]=SOLDIER
break
}
case WM_TIMER:
{
if(current_step<hrd.depth)
current_step++
else
{
current_step=0
KillTimer(hwnd,1)
Sleep(2000)
}
for( i=0i<5i++)
for( j=0j<4j++)
display_node[i][j]=hrd.out[current_step].state[i][j]
InvalidateRect(hwnd, NULL, 0)
break
}
case WM_COMMAND:
if(HIWORD(wParam)==BN_CLICKED)
switch (LOWORD(wParam))
{
case 1000:
{
//hrd= new hrd_Calculate
hrd.InitState(display_node)
if( hrd.SearchNode())
{
sprintf(s, "解题成功!\n\n解题深度：%d 节点数:%d", hrd.depth,hrd.totalnodes)
MessageBox(hwnd,s,"华容道",MB_OK)
hrd.OutputStep()
current_step=0
SetTimer(hwnd, 1,700, NULL)
}
else
{
sprintf(s,"此局无解")
MessageBox(hwnd,s,"华容道",MB_OK)
}
break
}
case 1001:
{
GetDlgItemText(hwnd,1002,str,80)
for (i=0i<5i++)
for(j=0j<4j++)
{
display_node[i][j]=(int)(str[m])-0x30
m++
}
InvalidateRect(hwnd, NULL, 1)
break
}
}
break
case WM_PAINT:
{
hdc = BeginPaint(hwnd,&pa)
PatBlt(memdc, 0, 0, rect.right, rect.bottom, PATCOPY)
//Draw
for (i=0i<5i++)
for(j=0j<4j++)
{
if (display_node[i][j]==SOLDIER)
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+1)*grid+j*interspace,initx+(i+1)*grid+i*interspace,arc,arc)
if (display_node[i][j]>=GENERAL1 && display_node[i][j]<=GENERAL5)
{
if (i<4)
if (display_node[i][j]==display_node[i+1][j])
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+1)*grid+j*interspace,initx+(i+2)*grid+(i+1)*interspace,arc,arc)
if (j<3)
if (display_node[i][j]==display_node[i][j+1])
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+2)*grid+(j+1)*interspace,initx+(i+1)*grid+i*interspace,arc,arc)
}
if (display_node[i][j]==CAOCAO)
if (i<4 &&j<3)
if( display_node[i+1][j+1]==CAOCAO)
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+2)*grid+(j+1)*interspace,initx+(i+2)*grid+(i+1)*interspace,arc,arc)
}
//////////////////////////////////
BitBlt(hdc,0,0,rect.right,rect.bottom,memdc,0,0,SRCCOPY)
EndPaint(hwnd,&pa)
break
}
case WM_DESTROY:
{
PostQuitMessage (0) /* send a WM_QUIT to the message queue */
DeleteDC(memdc)
DeleteObject(hbit)
break
}
default: /* for messages that we don't deal with */
return DefWindowProc (hwnd, message, wParam, lParam)
}
return 0
}
///HRD_Calculate.h 的程序写法
/////////////////////////////////////////////////
//华容道解法1.0.0.1
//此解法可得出最优解
//横刀立马 81步
//最后修改时间 2004.9.22 晚上
//
/////////////////////////////////////////////////
#include "HRD_Calculate.h"
hrd_calculate::hrd_calculate()
{
//申请状态表空间
first= new s_node[MAX_NODES]
}
hrd_calculate::~hrd_calculate()
{
delete[] first
}
void hrd_calculate::NodeToSNode(node * pnode,s_node* psnode)
{
int i,j
__int8 hgeneral=8,vgeneral=9
node * tnode= new node
*tnode=*pnode
for( i=0i<5i++)
for( j=0j<4j++)
{
if (tnode->state[i][j]>=GENERAL1 &&tnode->state[i][j]<=GENERAL5)
{
if (j<3)
if (tnode->state[i][j] == tnode->state[i][j+1])
{
tnode->state[i][j]=hgeneral
tnode->state[i][j+1]=hgeneral
}
if(i<4)
if(tnode->state[i][j] == tnode->state[i+1][j])
{
tnode->state[i][j]=vgeneral
tnode->state[i+1][j]=vgeneral
}
}
}
for( i=0i<5i++)
for( j=0j<4j++)
{
if(tnode->state[i][j]==hgeneral) tnode->state[i][j]=HGENERAL
if(tnode->state[i][j]==vgeneral) tnode->state[i][j]=VGENERAL
}
psnode->prior=(s_node *)pnode->prior
psnode->state=0
psnode->ext_state=0
for( i=0i<5i++)
for( j=0j<4j++)
{
psnode->state += pnode->state[i][j]
psnode->ext_state += tnode->state[i][j]
if (!(i==4 &&j==3)) psnode->state = psnode->state<<3
if (!(i==4 &&j==3)) psnode->ext_state = psnode->ext_state<<3
}
delete tnode
}
void hrd_calculate::SNodeToNode(s_node* psnode,node * pnode)
{
__int64 temp,s
s = psnode->state
pnode->prior=(node*)psnode->prior
for(int i=4i>=0i--)
for(int j=3j>=0j--)
{
temp = s &0x0000000000000007
pnode->state[i][j]= temp
s = s >>3
}
}
void hrd_calculate::OutputStep()
{
node * outfirst,* outlast,*p
outfirst=&out[0]
outlast=outfirst+(depth)
p=outlast
while ( p>=outfirst)
{
SNodeToNode(last,p)
last=last->prior
p--
}
}
bool hrd_calculate::SearchNode()
{
int nextnodes
node * tnode=new node
int total
while(true)
{
nextnodes=0
table[depth+1]=(unsigned int)(last+1)
for ( search<=current_last search++)
{
SNodeToNode(search,tnode)
tnode->prior=(node *)search
total=SearchOneNode(tnode)
nextnodes +=total
if (total==SUCCESS)
{
delete tnode
return true
}
}
if (nextnodes==0)
{
delete tnode
return false
}
depth++
current_last=last
}
}
int hrd_calculate::AddNode(node c)
{
s_node *p
s_node *snode=new s_node
if (depth<=3) p=first
else p=(s_node*)table[depth-1]
NodeToSNode(&c,snode)
for (p<=lastp++)
if (p->ext_state== snode->ext_state)
{
delete snode
return ADD_NO_NODE
}
//加入节点
last++
last->prior=snode->prior
last->state=snode->state
last->ext_state=snode->ext_state
totalnodes++
delete snode
if (c.state[3][1]==CAOCAO &&c.state[4][2]==CAOCAO )
return SUCCESS
else
return ADD_ONE_NODE
}
void hrd_calculate::InitState(unsigned __int8 state[5][4])
{
//设定初始状态
node initnode
initnode.prior=0 //没有上一步
for(int i=0i<5i++)
for(int j=0j<4j++)
initnode.state[i][j]=state[i][j]
////////////////////
NodeToSNode(&initnode,first)
////////////
last=first
search=first
current_last=first
depth=1
totalnodes=1
table[0]=0
table[depth]=(unsigned int)first
}
int hrd_calculate::SearchOneNode(node *c)
{
int i,j
int next_nodes=0
node t
for(i=0i<5i++)
for(j=0j<4j++)
{
if (c->state[i][j]==BLANK)
{
///////////////////////////////////////////////////////////////////////////////
//直走两步
if (j<3)
{
if (c->state[i][j+1]==BLANK)
{
if (j>0)//左边兵右移两格
{
if (c->state[i][j-1] == SOLDIER)
{
t=*c t.prior=c->prior
t.state[i][j-1]=BLANK
t.state[i][j+1]=SOLDIER
switch (AddNode(t))
{
case SUCCESS: return SUCCESS
case ADD_ONE_NODE: next_nodes++
}
}
}
if (j<2)//右边兵左移两格
{
if (c->state[i][j+2]==SOLDIER)
{
t=*c t.prior=c->prior
t.state[i][j+2]=BLANK
t.state[i][j]=SOLDIER
switch (AddNode(t))
{
case SUCCESS: return SUCCESS
case ADD_ONE_NODE: next_nodes++
}
}
}
if (j==2)//左边将右移两格
{
if (c->state[i][j-1]>=GENERAL1 &&c->state[i][j-1]<=GENERAL5 &&c->state[i][j-1]==c->state[i][j-2])
{
t=*c t.prior=c->prior
t.state[i][j]=c->state[i][j-1]
t.state[i][j+1]=c->state[i][j-1]
t.state[i][j-1]=BLANK
t.state[i][j-2]=BLANK
switch (AddNode(t))
{
case SUCCESS: return SUCCESS
case ADD_ONE_NODE: next_nodes++
}
}
}
if (j==0)//右边将左移两格
{
if (c->state[i][j+2]>=GENERAL1 &&c->state[i][j+2]<=GENERAL5 &&c->state[i][j+2]==c->state[i][j+3])
{
t=*c t.prior=c->prior
t.state[i][j]=c->state[i][j+2]
t.state[i][j+1]=c->state[i][j+2]
t.state[i][j+2]=BLANK
t.state[i][j+3]=BLANK
switch (AddNode(t))
{
case SUCCESS: return SUCCESS
case ADD_ONE_NODE: n
华容道的没有，但是可以告诉你怎么写物型。华容道其实是一个模拟过程，模拟色块的移动与结束斗缓状态的判定，你可以记录每个色块的左上角点的坐标，每次读到用户 *** 作的时候判定移动方向可行罩销猜否进行 *** 作。这些不是编程难点，华容道要想丰富主要是那些图片的存储，你可能要用到数据库的知识（如果你不止一张图的话），这样看东西就复杂了，不过大体上如果你不是做华容道的AI，这个程序还是很简单的，只是模拟而已。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）