题解 P2324 【[SCOI2005]骑士精神】

· · 题解

看到大家都用 A*, IDA*,本蒟蒻深深感受到了自己的弱小QAQ

其实这道题可以用BFS做，但是不是做15步内的BFS，而是做7-8步的BFS

那答案不是错的嘛？

我们从起始状态做一次BFS，再从结束状态做一个BFS，经过我们的计算打表，我们发现程序计算8步以内的结果非常快，所以我们做两次BFS之后，看两次结果序列的交集是否为空，若为空，则说明无解，否则有解

也就是双向BFS，感觉有点像Meet\ in\ Middle的思想

利用了把地图转换为一个字符串，然后用map存储的做法

//Copyright (c) 2019 by xiao_mmqueF. All Rights Reserved.
#include<bits/stdc++.h>
#define inl inline
#define reg register
#define INF 0x3f3f3f3f
using namespace std;
inl int read(){ int x=0,f=0; char ch=0; while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar(); return f?-x:x; }
inl void Ot(reg int x) { if(x<0)putchar('-'),x=-x; if(x>=10)Ot(x/10); putchar(x%10+'0'); }
inl void Print(reg int x,char til='\n'){Ot(x);putchar(til);}
inl int Max(reg int x,reg int y){return x>y?x:y;}
inl int Min(reg int x,reg int y){return x<y?x:y;}
inl int Abs(reg int x){return x<0?-x:x;} 
struct Node{
    int x, y;
    string s;
};
map<string, int> mp;
int mv[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
string aim="111110111100*110000100000";//目标状态
bool bfs(int x, int y, string s) {
    queue<Node> que;
    que.push((Node){x, y, s});
    mp[s]=1;
    while (!que.empty()) {
        Node h=que.front();
        que.pop();
        if (mp[h.s]==8) break;//8步就停
        if (h.s==aim) {
            Print(mp[h.s]-1);//8步内得到了答案
            return true;
        }
        for (int i=0; i<8; i++) {
            int xx=h.x+mv[i][0], yy=h.y+mv[i][1];
            if (xx<1 || xx>5 || yy<1 || yy>5) continue;
            string tmp=h.s;
            int tmp1=(h.x-1)*5+h.y, tmp2=(xx-1)*5+yy;
            char tmp_c=tmp[tmp1-1];
            tmp[tmp1-1]=tmp[tmp2-1];
            tmp[tmp2-1]=tmp_c;
            if (mp[tmp]==0) {
                mp[tmp]=mp[h.s]+1;
                que.push((Node){xx, yy, tmp});
            }
        }
    }
    return false;
}
void bfss(int x, int y, string s) {
    queue<Node> que;
    map<string, int> mpS;
    mp[s]=1;
    que.push((Node){x, y, s});
    mpS[s]=true;
    while (!que.empty()) {
        Node h=que.front();
        que.pop();
        if (mp[h.s]==9) {//步数到9了，说明总共超过了15步
            Print(-1);//返回无解
            return ;
        }
        for (int i=0; i<8; i++) {
            int xx=h.x+mv[i][0], yy=h.y+mv[i][1];
            if (xx<1 || xx>5 || yy<1 || yy>5) continue;
            string tmp=h.s;
            int tmp1=(h.x-1)*5+h.y, tmp2=(xx-1)*5+yy;
            char tmp_c=tmp[tmp1-1];
            tmp[tmp1-1]=tmp[tmp2-1];
            tmp[tmp2-1]=tmp_c;
            if (mp[tmp]!=0 && !mpS[tmp]) {//如果与第一次有交集
                cout << mp[tmp]-1+mp[h.s] << endl;
                return ;
            }
            if (!mpS[tmp]) {
                mp[tmp]=mp[h.s]+1;
                que.push((Node){xx, yy, tmp});
                mpS[tmp]=true;
            }
        }
    }
}

int main() {
    for(reg int T=read();T;T--) {
        mp.clear();
        string tmp, s="";
        int x, y;
        for (int i=1; i<=5; i++) {
            cin>>tmp;
            for (int j=0; j<5; j++)
                if (tmp[j]=='*') 
                    x=i, y=j+1;
            s+=tmp;//将开始状态作为字符串存储
        }
        if (!bfs(x, y, s)) bfss(3, 3, aim);
    }
    return 0;
}