个体工商户怎么做网站,wordpress主题源文件,网站没服务器行吗,南京 推广 网站建设1085: [SCOI2005]骑士精神 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1893 Solved: 1051Description 在一个55的棋盘上有12个白色的骑士和12个黑色的骑士#xff0c; 且有一个空位。在任何时候一个骑士都能按照骑士的走法#xff08;它可以走到和它横坐标相差为1 且有一个空位。在任何时候一个骑士都能按照骑士的走法它可以走到和它横坐标相差为1纵坐标相差为2或者横坐标相差为2纵坐标相差为1的格子移动到空位上。 给定一个初始的棋盘怎样才能经过移动变成如下目标棋盘 为了体现出骑士精神他们必须以最少的步数完成任务。 Input 第一行有一个正整数T(T10)表示一共有N组数据。接下来有T个5×5的矩阵0表示白色骑士1表示黑色骑士*表示空位。两组数据之间没有空行。 Output 对于每组数据都输出一行。如果能在15步以内包括15步到达目标状态则输出步数否则输出1。 Sample Input 2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100 Sample Output 7 -1 /*
迭代加深dfs经典题
记录目标状态然后从起始状态搜索。
爆搜可能超时要加剪枝
*/
#includecstdio
#includecstring
#includeiostream
#define limit 15
using namespace std;
int T,ans20,flag;
int xx[9]{0,-2,-2,-1,-1,1,1,2,2};
int yy[9]{0,-1,1,-2,2,2,-2,1,-1};
int s[10][7],get[10][10];
int target[10][10];
char si;void get_t()//记录目标状态
{target[1][1]1;target[1][2]1;target[1][3]1;target[1][4]1;target[1][5]1;target[2][1]0;target[2][2]1;target[2][3]1;target[2][4]1;target[2][5]1;target[3][1]0;target[3][2]0;target[3][3]2;target[3][4]1;target[3][5]1;target[4][1]0;target[4][2]0;target[4][3]0;target[4][4]0;target[4][5]1;target[5][1]0;target[5][2]0;target[5][3]0;target[5][4]0;target[5][5]0;
}int Judge()//计算当前状态与目标状态至少还有多少步
{int ret0;for(int i1;i5;i)for(int j1;j5;j){if(s[i][j]!target[i][j])ret;}return ret;
}void DFS(int now,int x,int y,int sum)
{if(flag) return;int cJudge();if(nowsum){if(c0)flag1,anssum;}if(now-1csum) return;//最优性剪枝当前的步数差异限制步数 for(int i1;i8;i){int nxxxx[i];int nyyyy[i];if(nx0nx5ny0ny5){swap(s[x][y],s[nx][ny]);DFS(now1,nx,ny,sum);swap(s[x][y],s[nx][ny]);}}
}int main()
{scanf(%d,T);get_t();while(T--){int x,y;for(int i1;i5;i)for(int j1;j5;j){cinsi;if(si*){xi;yj;get[i][j]2;} else get[i][j]si-0;}for(int k0;klimit;k)//迭代加深限制步数 {flag0;ans20;for(int i1;i5;i)for(int j1;j5;j)s[i][j]get[i][j];DFS(0,x,y,k);if(ansk) break;}if(ans15)printf(%d\n,ans);else printf(-1\n);}return 0;
} 心若向阳无谓悲伤 转载于:https://www.cnblogs.com/L-Memory/p/6159812.html
