uva10422

题目大意：
跟国际象棋中的骑士的走法差不多，是走日字型的。找到空格，从空格开始走，这题是用回溯+剪枝做的。计算它没有达到目标位置的数量，如果数量等于0的话就用一个变量保存下来值与其他同样满足的值进行比较。如果不等于0的话，它每走一步最多改变的是两个位置的状态，那么如果走了（sum+1）/2+step 是所需要走的最少的步数如果大于原来的最少值的话 就直接返回。（这一步是很重要的剪枝）

代码：

#include 
using namespace std;
#include 
#include 
#include //int grid[5][5];//queue q;
int _min;
int des[5][5] = {{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0,}};
int grid[5][5];
//int move[8][2] = {{1,2},{-1,2},{2,1},{2,-1},{-2,1},{-2,-1},{1,-2},{-1,-2}};
int move1[8][2]={{-1,-2},{-1,2},{-2,1},{-2,-1},{2,1},{2,-1},{1,-2},{1,2}};
void dfs(int x,int y,int step,int pos) {
//  cout << "1" ;int sum = 0,temp,x1,y1;if(step >= _min)return;for(int i = 0 ; i < 5; i++) for(int j = 0 ; j < 5; j++)if(grid[i][j] != des[i][j]) ++sum;
//  printf("%d ",sum);if(sum == 0) {if(step < _min)_min = step;//printf("1");return;}if((sum+1)/2 + step >= _min)return;for(int i = 0; i < 8; i++) {x1 = x + move1[i][0];y1 = y + move1[i][1];if((x1 >= 0) && (x1 <5) && (y1 >=0) && (y1 <5) && ((pos+i) != 7)) {temp = grid[x1][y1];grid[x1][y1] = grid[x][y];grid[x][y] = temp;dfs(x1,y1,step+1,i);temp = grid[x1][y1];grid[x1][y1] = grid[x][y];grid[x][y] = temp;}}}int main() {int T;scanf("%d",&T);getchar();char s[6];int x,y;while(T--) {for(int i = 0 ; i < 5; i++) {gets(s);for(int j = 0 ; s[j]!= '\0'; j++) {if(s[j] == ' ') {x = i; y = j;grid[i][j] = 2;}else grid[i][j] = s[j] -'0'; //          printf("%d",grid[i][j]);}//      cout <}_min = 11;dfs(x,y,0,8);   if(_min  > 10) printf("Unsolvable in less than 11 move(s).\n");elseprintf("Solvable in %d move(s).\n",_min);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！