C/C++教程

C++代码破解曹瞒走华容道(广搜、状态压缩、二叉排序树)

本文主要是介绍C++代码破解曹瞒走华容道(广搜、状态压缩、二叉排序树),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题描述

6×6的网格内,有竖条和横条,长度为2或3 竖条只能上下移动,横条只能左右移动 在给定步数内,使得绿色横条(即曹阿瞒有我良计取冀州便是易如反掌 )到达右端
(不想看只想要代码的点我)

![Alt](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hdmF0YXIuY3Nkbi5uZXQvNy83L0IvMV9yYWxmX2h4MTYzY29tLmpwZw在这里插入图片描述

首先建模,输入如下:

每行输入(x,y,dir,len)分别代表横条在第x行和第y列,dir为1代表为横条,为0代表竖条,len为横条的长度,最后一行以(-1,-1,-1,-1)结尾
然后输入步数step,要求在step内得到结果

输出:若有解,输出路径

样例1:

2 0 1 2
0 3 1 3
1 4 0 2
3 4 0 3
-1 -1 -1 -1
3
OOOBBB
OOOOCO
AAOOCO
OOOODO
OOOODO
OOOODO

BBBOOO
OOOOCO
AAOOCO
OOOODO
OOOODO
OOOODO

BBBOCO
OOOOCO
AAOOOO
OOOODO
OOOODO
OOOODO

BBBOCO
OOOOCO
OOOOAA
OOOODO
OOOODO
OOOODO

Success

样例2:

2 0 1 2
0 1 0 2
0 2 1 2
0 5 0 3
1 2 0 3
3 0 0 3
3 3 1 3
4 1 1 2
4 4 0 2
-1 -1 -1 -1
22
OBCCOD
OBEOOD
AAEOOD
FOEGGG
FHHOLO
FOOOLO

OBOCCD
OBEOOD
AAEOOD
FOEGGG
FHHOLO
FOOOLO
...(鉴于篇幅,省略)

CCEOLO
OOEOLO
OOEOAA
FGGGOD
FBOHHD
FBOOOD

Success

解:(1)状态压缩:棋盘一共6×6大小,也就是最多只有3 * 6 = 18个横条或竖条,每个横条的行数x固定,y变化,每个竖条的y固定,x变化,也就是说,可以用3位的数来表示横条的状态,long long 的数字类型一共有64位,也就是说我们可以用一个long long int 的数来代表棋盘的一个状态。
做法:图压缩成数的函数:

long compress()       //将当前状态压缩到long 
{
	long ans = 0;
//	cout<<batch_num<<'*';
	for(int i = 1;i <= batch_num;i++)
	{
		if(batches[i].dir)
			ans = ans | batches[i].y;
		else
			ans = ans | batches[i].x;
		if(i != batch_num)
		ans = ans << 3;
//		cout<<ans<<endl;
	}
	return ans;
}

(2)二叉排序树:将每个状态记录到二叉排序树里,查找的效率在O(logn),每次查一个状态是否已经出现过的时候,速度很快。
(3)横条竖条移动的模拟:这个简单。
(4)带路径记录的广搜:对解答树进行层优先遍历,用二维数组path[x][y]记录路径,x代表step,即解答树的层数。

void bfs(long s)
{
	BSTNode *root = NULL;
	queue<PathStep> q;
	q.push(PathStep(s,step,path[step].size()));
	path[step].push_back(make_pair(s,-1));
	Insert(&root,s);
	while(!q.empty())
	{
		PathStep now = q.front();q.pop();
		if(now.step < 0)
			continue;
		
		validate_state(now.state);
		if(mapp[2][5] == 1)
		{
			int now_step = now.step;
			int pre_num = now.num;
			long answer[30];
			answer[0] = now.state;
			int i = 1;
			while(now_step < step && pre_num != -1)
			{
//				cout<<path[now_step + 1][pre_num].first;
//				validate_state(path[now_step + 1][pre_num].first);
//				print();
				answer[i++] = path[now_step + 1][pre_num].first;
				pre_num = path[now_step + 1][pre_num].second;
				now_step++;
			}
			for(int k = i - 1;k >= 0;k--)
			{
				validate_state(answer[k]);
				print();
			}
			cout<<"Success"<<endl;
			return;
		}
		
		for(int i = 1;i <= batch_num;i++)
		{
			if(batches[i].dir)
			{
				if(move(i,3) != -1 || move(i,4) != -1)
				{
					long stt = compress();
					if(validate_state(stt))
					{
//						cout<<"1111111111111111"<<endl;
//						print();
						BSTNode *p;
						if(!Search(root,stt,NULL,&p))
						{
							Insert(&root,stt);
							q.push(PathStep(stt,now.step - 1,path[now.step - 1].size()));	
							path[now.step - 1].push_back(make_pair(stt,now.num));
						}
					}
					validate_state(now.state);
				}
			}
			else
			{
				if(move(i,1) != -1 || move(i,2) != -1)
				{
					long stt = compress();
					if(validate_state(stt))
					{
//						cout<<"2222222222222"<<endl;
//						print();
						BSTNode *p;
						if(!Search(root,stt,NULL,&p))
						{
							Insert(&root,stt);
							q.push(PathStep(stt,now.step - 1,path[now.step - 1].size()));
							path[now.step - 1].push_back(make_pair(stt,now.num));	
						}
					}
					validate_state(now.state);
				}
			}
		}

	}
	cout<<"failed"<<endl;
}
这篇关于C++代码破解曹瞒走华容道(广搜、状态压缩、二叉排序树)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!