Bzoj 1085: [SCOI2005]骑士精神 (dfs)

Bzoj 1085: [SCOI2005]骑士精神

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1085

dfs + 剪枝.

剪枝方法:

1.每次交换只能改变一个位置.若发现之间相差的步数加上以前走的步数大于15的话,直接舍弃这一状态.

2.初始时,\(ans\)设为\(16\)

有了上面两个剪枝就A了.

照这节奏,SCOI2005就刷完了???

#include <iostream>

#include <cstdio>

#define X 6

using namespace std;

const int gx[] = {0,-2,-2,-1,-1,1,1,2,2};

const int gy[] = {0,-1,1,-2,2,-2,2,-1,1};

char map[X][X];

char c[X][X] = {

    '0','0','0','0','0','0',

    '0','1','1','1','1','1',

    '0','0','1','1','1','1',

    '0','0','0','*','1','1',

    '0','0','0','0','0','1',

    '0','0','0','0','0','0'

};

int ans;

int inint(){

    int num = 0;

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

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

            if(c[i][j] != map[i][j])num ++;

        }

    }

    return num;

}

void dfs(int x,int y,int d,int tmp){

    int l = inint();

    if(d + l > 16)return;

    if(d > ans)return;

    if(l == 0) ans = d;

    for(int i = 1;i <= 8;++ i){

        if(x + gx[i] < 1 || x + gx[i] > 5)continue;

        if(y + gy[i] < 1 || y + gy[i] > 5)continue;

        if(tmp + i == 9)continue;

        swap(map[x][y],map[x + gx[i]][y + gy[i]]);

        dfs(x + gx[i],y + gy[i],d + 1,i);

        swap(map[x][y],map[x + gx[i]][y + gy[i]]);

    }

}

void work(){

    int x,y;

    for(int i = 1;i <= 5;++ i)cin >> map[i] + 1;

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

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

            if(map[i][j] == '*')

                x = i,y = j;

        }

    }

    ans = 16;

    dfs(x,y,0,0);

    printf("%d\n",ans == 16 ? -1 : ans);

    return;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t --){

        work();

    }

    return 0;

}