建网站和开发网站,网站建设方案书模板 备案,wordpress 数据调用api,wordpress登陆函数题目 此题根据题目可知是迭代加深搜索。 首先应该枚举空格的位置#xff0c;让空格像一个马一样移动。 但迭代加深搜索之后时间复杂度还是非常的高#xff0c;根本过不了题。 感觉也想不出什么减枝#xff0c;于是便要用到了乐观估计函数#xff08;Optimistic Estimation … 题目 此题根据题目可知是迭代加深搜索。 首先应该枚举空格的位置让空格像一个马一样移动。 但迭代加深搜索之后时间复杂度还是非常的高根本过不了题。 感觉也想不出什么减枝于是便要用到了乐观估计函数Optimistic Estimation Function 以3种颜色的格子来表示原棋盘 如果我们要从一个状态抵达到原棋盘那么需要的步数绝对是小于当前状态与原棋盘不同的格子的数量、 那么我们的乐观估计函数就出来了。如果当前状态与原棋盘的不同格子数量小于我们的剩余的步数那么肯定是抵达不了的return回去就行。 代码 #include iostream
#include cstring
using namespace std;#define N 510int dir[8][2]{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,-2},{-1,2}};
int fuck[10][10]{{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1},{0,0,0,0,0,1}};
int a[10][10],T,px,py,len,flag0;int dif() {int sum0;for(int i1;i5;i) for(int j1;j5;j)if(a[i][j] ! fuck[i][j]) sum;return sum;
}void dfs(int step) {if(steplen) {if(dif()0) flag1;return ;}if(dif()len-step2) return ;for(int k0;k8;k) {int txpxdir[k][0],typydir[k][1];if( tx1 || tx5 || ty1 || ty5) continue;swap(a[tx][ty],a[px][py]);swap(px,tx);swap(py,ty);dfs(step1);swap(a[tx][ty],a[px][py]);swap(px,tx);swap(py,ty);}
}int main() {cinT;while(T--) {flag0;memset(a,0,sizeof(a)); for(int i1;i5;i) for(int j1;j5;j) {char l;cinl;if(l1) a[i][j]1;else if(l0) a[i][j]0;else a[i][j]2,pxi,pyj;}for(len0;len15;len) {dfs(1);if(flag) {coutlenendl;break;}}if(!flag)cout-1endl;}
} 在我的程序里有这一句 if(dif()len-step2) return ; 因为有这种特例保险起见多加一个1。 转载于:https://www.cnblogs.com/MisakaMKT/p/10769866.html
