洛谷 P2324 [SCOI2005]骑士精神 题解

2019/03/01 23:22
阅读数 5

题目传送门

题目

题目描述

输入输出格式

输入格式:

第一行有一个正整数T(T<=10),表示一共有N组数据。接下来有T个5×5的矩阵,0表示白色骑士,1表示黑色骑士,*表示空位。两组数据之间没有空行。

输出格式:

对于每组数据都输出一行。如果能在15步以内(包括15步)到达目标状态,则输出步数,否则输出-1。

 

输入输出样例

输入样例:

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
输出样例: 
7
-1

说明

 

题目大意

有一个棋盘,上面有一些黑马和白马,问最少多少步能到达目标状态

 

思路

一道有点难(也许只有我这么认为)的搜索题目

题目说只要求15步之内的最小步数,超出了就不用算

可以从1到15枚举(或二分)答案,用dfs判断答案是否可行

在这题中,考虑空格的位置来搜索比较方便(毕竟只有一个空格)

 

考虑剪枝

1: 在搜索时记录与目标状态不同的不同的方格个数,因为除了最后一步可以一步将两个不正确的格子变为正确,其他时候每一步都只能将一个格子更正

所以如果 当前已经走的步数 + 状态不对的格子数 - 1 > 限定的答案 直接return (注意:这里一定要-1)

if (now + ss - 1 > maxn) return false;  //剪枝 1 :如果当前预计的最少步数已经超过限定的值,停止 
//由于最后一步可以一下更正两格,所以最少步数为 now + ss - 1

2:不走回头路,如果走回去就continue

在实现时将八个方向按照一定顺序搜索,进行判断

int dx[8] = {-2, -2, -1, 1, -1, 1, 2, 2}, dy[8] = {-1, 1, 2, 2, -2, -2, -1, 1}; 
//dx,dy按照一定的顺序来,便于判断是否走回去 
for (int i = 0; i < 8; i++) //8个方向搜索 
{
	if (i + last == 7) continue;  //如果走第i个方向是往回走就不用搜索了(这就是为什么dx和dy要有一定顺序) 
		
}

 

搜索方法

空格每次回与一个白马或黑马交换位置:

考虑马

情况1:如果一个马原本在正确的位置,交换后位置错误,则状态不同的格子数 + 1;

情况2:和情况1相反,一个马从错误位置换到了正确位置,则状态不同的格子数 - 1;

考虑空格

情况3:如果一个空格原本在正确的位置,交换后位置一定错误,则状态不同的格子数 + 1;

情况4:和情况3相反,一个空格从错误位置换到了正确位置,则状态不同的格子数 - 1;

if (ch[xx][yy] == m[xx][yy] and ch[xx][yy] != m[x][y]) tmp++; //上述情况1 
else if (ch[xx][yy] != m[xx][yy] and ch[xx][yy] == m[x][y]) tmp--; //情况2 
if (m[x][y] == '*') tmp++; //情况3 
else if (m[xx][yy] == '*') tmp--; //情况4

 

完整代码

#include <bits/stdc++.h>
using namespace std;
int t, sx, sy, s, maxn, ans;
int dx[8] = {-2, -2, -1, 1, -1, 1, 2, 2}, dy[8] = {-1, 1, 2, 2, -2, -2, -1, 1}; 
//dx,dy按照一定的顺序来,便于判断是否走回去 
char ch[5][5];
char m[5][5]={ {'1', '1', '1', '1', '1'},
               {'0', '1', '1', '1', '1'},
               {'0', '0', '*', '1', '1'},
               {'0', '0', '0', '0', '1'},
               {'0', '0', '0', '0', '0'}}; 
//打表便于对比状态 
bool ok (int x, int y, int now, int ss, int last)
//x,y表示坐标,now表示当前步数,ss表示预计最少步数,last表示上一次走的方向 
{
	if (now + ss - 1 > maxn) return false;  //剪枝  :如果当前预计的最少步数已经超过限定的值,停止 
	//由于最后一步可以一下更正两格,所以最少步数为 now + ss - 1
	if (!ss) {ans = now;  return true;}  //如果当前状态就是目标状态,记录答案,返回true 
	for (int i = 0; i < 8; i++) //8个方向搜索 
	{
		int tmp = ss;
		if (i + last == 7) continue;  //如果走第i个方向是往回走就不用搜索了(这就是为什么dx和dy要有一定顺序) 
		int xx = x + dx[i], yy = y + dy[i];
		if (xx < 0 or xx > 4 or yy < 0 or yy > 4) continue;
		if (ch[xx][yy] == m[xx][yy] and ch[xx][yy] != m[x][y]) tmp++; //上述情况1 
		else if (ch[xx][yy] != m[xx][yy] and ch[xx][yy] == m[x][y]) tmp--; //情况2 
		if (m[x][y] == '*') tmp++; //情况3 
		else if (m[xx][yy] == '*') tmp--; //情况4 
		swap (ch[x][y], ch[xx][yy]);
		bool k = ok (xx, yy, now + 1, tmp, i);
		if (k) return true;
		swap (ch[x][y], ch[xx][yy]); //回溯 
	}
	return false;
}  
int main()
{
	scanf ("%d", &t);
	while (t--)
	{
		s = 0, ans = -1;
		for (int i = 0; i < 5; i++)
		  for (int j = 0; j < 5; j++)  {
		  	cin >> ch[i][j];
		  	if (ch[i][j] == '*') sx = i, sy = j;
		  	if (ch[i][j] != m[i][j]) s++; //如果和目标不同,统计加 1 
		  }
		for (int i = s; i <= 15; i++){  
			maxn = i;
			if (ok (sx, sy, 0, s, 10))  break;
		}	
		printf ("%d\n", ans);
	}
	return 0;
}

点一下左边的推荐吧!谢谢~~~

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部