題目所屬： 隱式圖的搜索
題目意思： 給定一個5 x 5 的棋盤，棋盤上面有12個黑色的棋子和12個白色的棋子和一個空格， 最開始的這些棋子的位置是不定的， 要求我們找到最小的步數去把這個棋盤轉化為最後的那個樣子，最後輸出。
解題思路： 我們容易相到的是直接bfs去搜索求出最小步數，但是這一題也可以用dfs+回溯做。首先我們開一個Fin數組用來保存最後的位置，然後就是我們對空格周圍的8個方向進行一一的深搜回溯，我們每進行一次搜索就判斷是否當前以及到達最後的位置（這個通過judge函數判斷），如果是那麼判斷能否更新ans。其中我們還可以進行優化，就是對於Tans > 10的搜索肯定都是沒用的那麼我們就可以直接捨去。還有這一題的每個點是可以重復走的因為每一次可能空格周圍的點就不同，所以不用去開vis數組來標記是否走過
代碼：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
int Fin[5][5] = {//保存最後的結果
{1, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, -1, 1, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
};
int dir[8][2] = {//方向數組
{-2, -1},
{-2, 1},
{-1, 2},
{1, 2},
{2, 1},
{2, -1},
{1, -2},
{-1, -2}
};
int G[5][5]; //保存輸入的位置
char ch;
int t, ans;
struct Point {//坐標結構體
int x;
int y;
};
//判斷是否到最後的位置
int judge(){
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < 5 ; j++){
if(G[i][j] != Fin[i][j])//只要有不像同的就return 0
return 0;
}
}
return 1;
}
//深搜回溯
void dfs(int x , int y , int Tans){//傳入三個參數坐標以及步數
if(Tans > 10) return;//大於10步的都不用搜索
if(judge()){//如果這時候滿足了，那麼判斷ans是否大於Tans
if(ans > Tans) ans = Tans;
return;
}
for (int i = 0; i < 8; i++) {//8個方向搜索
if (dir[i][0]+x < 0 || dir[i][0]+x >= 5) continue;//越界就繼續下一個方向
if (dir[i][1]+y < 0 || dir[i][1]+y >= 5) continue;//越界就繼續下一個方向
swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//將空格位置交換
dfs(x+dir[i][0] , y+dir[i][1] , Tans+1);//遞歸繼續搜索
swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//空格從新移回
}
}
//主函數
int main() {
scanf("%d%*c", &t);
while (t--) {
Point p;
//處理輸入
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < 5 ; j++){
if(j == 4) scanf("%c%*c" , &ch);
if(j < 4) scanf("%c" , &ch);
if(ch == ' '){
G[i][j] = -1;
p.x = i ; p.y = j;
}
else G[i][j] = ch-'0';
}
}
ans = 999999999;
dfs(p.x , p.y , 0);
if (ans > 10) printf("Unsolvable in less than 11 move(s).\n");
else printf("Solvable in %d move(s).\n", ans);
} www.2cto.com
return 0;
}
