题意

中文题意。

思路

首先找到空白的格子，因为空白的格子可以和其他的骑士换。从空白的点开始搜索，每次和其他点交换。因为最多只有十五步，可以做16次搜索，搜索的时候，记录走过的步数和至少剩余的步数（还剩下多少个骑士不在原本的位置），这样剪枝。当check到所有的骑士都在合法位置的时候，就可以确定答案了。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;

typedef long long LL;

int init[6][6] = {

    {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}

};

char mm[7][7];

int mp[7][7], ans;

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

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

int check() {

    int cnt = 0;

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

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

            if(mp[i][j] != init[i][j]) cnt++;

    return cnt;

}

void A_Star(int x, int y, int g, int now) {

    if(g == now) {

        if(check() == 0) ans = now;

        return ;

    }

    if(~ans) return ;

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

        int nx = x + dx[i], ny = y + dy[i];

        if(nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;

        swap(mp[nx][ny], mp[x][y]);

        if(check() + g <= now) A_Star(nx, ny, g + 1, now);

        swap(mp[nx][ny], mp[x][y]);

    }

}

int main() {

    int t; scanf("%d", &t);

    while(t--) {

        for(int i = 0; i < 5; i++) scanf("%s", mm[i]);

        int ix, iy;

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

            mp[i][j] = mm[i][j] - '0';

            if(mm[i][j] == '*') mp[i][j] = 2, ix = i, iy = j;

        }

        ans = -1;

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

            A_Star(ix, iy, 0, i);

            if(~ans) break;

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

BZOJ 1085：[SCOI2005]骑士精神（A*算法）

题意

思路

最新文章

热门文章