BZOJ 1085: [SCOI2005]骑士精神

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

　　在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑
士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空
位上。给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步
数完成任务。

Input

　　第一行有一个正整数T(T<=10)，表示一共有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状态很多，我们考虑剪枝/控制搜索层数。

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int N;
short int goalMap[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}};
short int nowMap[5][5];
int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={-2,-1,1,2,2,1,-1,-2};
char x;
int Ans;
bool isSuccess;
inline char read(){
    x=getchar();
    while(x!='0' && x!='1' && x!='*') x=getchar();
    return x;
}
inline bool isAvailable(int now){
    int res=0;
    for (int i=0;i<5;i++)
        for (int j=0;j<5;j++)
            if (goalMap[i][j]!=nowMap[i][j]){
                res++;
                if (res+now>Ans) return false;
            }
    return true;
}
inline bool check(){
    for (int i=0;i<5;i++)
        for (int j=0;j<5;j++)
            if(goalMap[i][j]!=nowMap[i][j]) return false;
    return true;
}
inline void swap(int &x,int &y){
    int c=x;
    x=y;
    y=c;
}
void DFS(int lx,int ly,int now){
    /*
    for (int i=0;i<5;i++){
        for (int j=0;j<5;j++){
            if (nowMap[i][j]==-1) printf("*"); else printf("%d",nowMap[i][j]);
        }
        printf("n");
    }
    printf("n");
    */
    if (now==Ans){
        if (check()) isSuccess=true;
        return;
    }
    if (isSuccess) return ;
    for (int k=0;k<8;k++){
        int tx=lx+dx[k],ty=ly+dy[k];
        if (tx>=0 && tx<5 && ty>=0 && ty<5){
            swap(nowMap[lx][ly],nowMap[tx][ty]);
            if(isAvailable(now)) DFS(tx,ty,now+1);
            swap(nowMap[lx][ly],nowMap[tx][ty]);
        }
    }
}
inline void solveProblem(){
    int lx,ly;
    char ix;
    isSuccess=false;
    for (int i=0;i<5;i++){
        for (int j=0;j<5;j++){
            ix=read();
            if (ix=='1')
                nowMap[i][j]=1;
            else if (ix=='0')
                nowMap[i][j]=0;
            else{
                nowMap[i][j]=-1;
                lx=i;ly=j;
            }
        }
    }
    for (Ans=1;Ans<=15;Ans++){
        DFS(lx,ly,0);
        if (isSuccess) break;
    }
    if (isSuccess)  printf("%dn",Ans); else printf("-1n");
}
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;i++) solveProblem();
    return 0;
}

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int N;

short int goalMap[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}};

short int nowMap[5][5];

int dx[]={1,2,2,1,-1,-2,-2,-1};

int dy[]={-2,-1,1,2,2,1,-1,-2};

char x;

int Ans;

bool isSuccess;

inline char read(){

x=getchar();

while(x!='0' && x!='1' && x!='*') x=getchar();

return x;

}

inline bool isAvailable(int now){

int res=0;

for (int i=0;i<5;i++)

for (int j=0;j<5;j++)

if (goalMap[i][j]!=nowMap[i][j]){

res++;

if (res+now>Ans) return false;

}

return true;

}

inline bool check(){

for (int i=0;i<5;i++)

for (int j=0;j<5;j++)

if(goalMap[i][j]!=nowMap[i][j]) return false;

return true;

}

inline void swap(int &x,int &y){

int c=x;

x=y;

y=c;

}

void DFS(int lx,int ly,int now){

for (int i=0;i<5;i++){

for (int j=0;j<5;j++){

if (nowMap[i][j]==-1) printf("*"); else printf("%d",nowMap[i][j]);

}

printf("n");

}

printf("n");

if (now==Ans){

if (check()) isSuccess=true;

return;

}

if (isSuccess) return ;

for (int k=0;k<8;k++){

int tx=lx+dx[k],ty=ly+dy[k];

if (tx>=0 && tx<5 && ty>=0 && ty<5){

swap(nowMap[lx][ly],nowMap[tx][ty]);

if(isAvailable(now)) DFS(tx,ty,now+1);

swap(nowMap[lx][ly],nowMap[tx][ty]);

}

inline void solveProblem(){

int lx,ly;

char ix;

isSuccess=false;

for (int i=0;i<5;i++){

for (int j=0;j<5;j++){

ix=read();

if (ix=='1')

nowMap[i][j]=1;

else if (ix=='0')

nowMap[i][j]=0;

else{

nowMap[i][j]=-1;

lx=i;ly=j;

}

for (Ans=1;Ans<=15;Ans++){

DFS(lx,ly,0);

if (isSuccess) break;

}

if (isSuccess) printf("%dn",Ans); else printf("-1n");

}

int main(){

scanf("%d",&N);

for (int i=1;i<=N;i++) solveProblem();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑