1085: [SCOI2005]騎士精神

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?2838??Solved:?1663
[Submit][Status][Discuss]

Description

　　在一個5×5的棋盤上有12個白色的騎士和12個黑色的騎士， 且有一個空位。在任何時候一個騎士都能按照騎
士的走法（它可以走到和它橫坐標相差為1，縱坐標相差為2或者橫坐標相差為2，縱坐標相差為1的格子）移動到空
位上。 給定一個初始的棋盤，怎樣才能經過移動變成如下目標棋盤： 為了體現(xiàn)出騎士精神，他們必須以最少的步
數(shù)完成任務。

Input

　　第一行有一個正整數(shù)T(T<=10)，表示一共有N組數(shù)據(jù)。接下來有T個5×5的矩陣，0表示白色騎士，1表示黑色騎
士，*表示空位。兩組數(shù)據(jù)之間沒有空行。

Output

　　對于每組數(shù)據(jù)都輸出一行。如果能在15步以內（包括15步）到達目標狀態(tài)，則輸出步數(shù)，否則輸出－1。

Sample Input

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

Sample Output

7
-1

直接搜肯定超時，狀態(tài)有很多種

考慮到每次移動最多多增一個匹配位置，我們其實在搜索的時候可以估計最少還剩多少步搜到，如果不滿足條件就退出

這就是A*算法啦

為了加快速度，我們可以枚舉所需步數(shù)，分15次搜，搜到則停

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long int #define REP(i,n) for (int i = 1; i <= (n); i++) #define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next) using namespace std; const int maxn = 100005,maxm = 100005,INF = 1000000000; int ans[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 a[5][5],X[8] = {-1,-2,-2,-1,1,2,2,1},Y[8] = {-2,-1,1,2,2,1,-1,-2}; int k; bool flag; bool judge(){for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)if (a[i][j] != ans[i][j]) return false;return true; } bool check(int s){int cnt = 0;for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)if (a[i][j] != ans[i][j]) {cnt++;if (cnt + s > k) return false;}return true; } void dfs(int s,int x,int y){if (s == k) {if (judge()) flag = true; return;}int nx,ny;for (int i = 0; i < 8; i++){nx = x + X[i]; ny = y + Y[i];if (nx < 0 || ny < 0 || nx > 4 || ny > 4) continue;swap(a[x][y],a[nx][ny]);if (check(s)) dfs(s + 1,nx,ny);swap(a[x][y],a[nx][ny]);} } int main(){int Tim;cin>>Tim;while (Tim--){memset(a,0,sizeof(a)); flag = false;char c; int x,y;for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++){c = getchar();while (c != '1' && c != '0' && c != '*') c = getchar();if (c == '*') a[i][j] = 2,x = i,y = j;else a[i][j] = c - '0';}for (k = 1; k <= 15; k++){dfs(0,x,y);if (flag){printf("%d\n",k);break;}}if (!flag) printf("-1\n");}return 0; }

轉載于:https://www.cnblogs.com/Mychael/p/8282783.html

總結

以上是生活随笔為你收集整理的BZOJ 1085 [SCOI2005]骑士精神 【A*启发式搜索】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。