× 19 Time Limit Exceeded
查看原帖
× 19 Time Limit Exceeded
1220130
520_forever_love_you楼主2024/7/9 15:06

求调代码,使用迭代加深法完成此题,但只能通过44个点,其余全部超时。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long MAXN = 10005;
string s, t;
int ok;
map<string, int> vis;
queue<string> q;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void dfs(string u, int cur, int lim){
    if(cur > lim)    return ;
    if(ok)    return ;
    if(u == t){
        cout << lim << '\n';
        ok = 1;
        return ;
    }
    int p = u.find('0');
    int x = p / 3;
    int y = p % 3;
    for(ll i = 0; i < 4; i++){
        string v = u;
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx > 2 || ny > 2)    continue;
        int id = nx * 3 + ny;
        swap(v[p], v[id]);
        dfs(v, cur + 1, lim);
    }
}

signed main(){
    cin >> s;
    t = "123804765";
    for(ll i = 0; ; i++){
        dfs(s, 0, i);
        if(ok)    break;
    }
    return 0;
}
2024/7/9 15:06
加载中...