Can anyone help me? I’m having trouble with this question. I’ve been trying for an entire afternoon, but always get TLE. I started with brute force BFS, and later switched to bidirectional BFS, but it still times out. Thank you very much!!!
#include<bits/stdc++.h>
using namespace std;
using sta = array<int, 4>;
using ll = long long;
const int n = 70;
int t, a, b, c, d;
struct my_hash {
size_t operator() (const sta &x) const {
ll hash_val = (ll)x[0] * (n + 1) * (n + 1) * (n + 1) +
(ll)x[1] * (n + 1) * (n + 1) +
(ll)x[2] * (n + 1) +
(ll)x[3];
return hash<ll>()(hash_val);
}
};
int bfs(sta &x, unordered_map<sta, int, my_hash> &dis1, unordered_map<sta, int, my_hash> &dis2, queue<sta> &q) {
for(int i = 0; i < x.size(); i++) {
int l = x[i] - 1;
if(l >= 1) {
bool flag = 0;
for(int k = 0; k < 4; k++) {
if(k != i && x[k] == l) {
flag = 1;
break;
}
}
if(!flag) {
sta nxt = x;
nxt[i] = l;
sort(nxt.begin(), nxt.end());
if(dis2.count(nxt)) {
return dis2[nxt] + dis1[x] + 1;
}
if(dis1.find(nxt) == dis1.end()) {
dis1[nxt] = dis1[x] + 1;
q.push(nxt);
}
}
}
int r = x[i] + 1;
if(r <= n) {
bool flag = 0;
for(int k = 0; k < 4; k++) {
if(k != i && x[k] == r) {
flag = 1;
break;
}
}
if(!flag) {
sta nxt = x;
nxt[i] = r;
sort(nxt.begin(), nxt.end());
if(dis2.count(nxt)) {
return dis2[nxt] + dis1[x] + 1;
}
if(dis1.find(nxt) == dis1.end()) {
dis1[nxt] = dis1[x] + 1;
q.push(nxt);
}
}
}
}
for(int i = 0; i < x.size(); i++) {
for(int j = 0; j < x.size(); j++) {
if(i == j) continue;
int op = x[j] * 2 - x[i];
if(op >= 1 && op <= n) {
bool flag = 0;
for(int k = 0; k < 4; k++) {
if(k != i && op == x[k]) {
flag = 1;
break;
}
}
if(!flag) {
sta nxt = x;
nxt[i] = op;
sort(nxt.begin(), nxt.end());
if(dis2.count(nxt)) {
return dis2[nxt] + dis1[x] + 1;
}
if(dis1.find(nxt) == dis1.end()) {
dis1[nxt] = dis1[x] + 1;
q.push(nxt);
}
}
}
}
}
return -1;
}
void solve() {
cin >> a >> b >> c >> d;
sta st = {1, 2, 3, 4};
sta ed = {a, b, c, d};
sort(ed.begin(), ed.end());
queue<sta> q1;
queue<sta> q2;
unordered_map<sta, int, my_hash> dis1, dis2;
dis1[st] = 0;
dis2[ed] = 0;
q1.push(st);
q2.push(ed);
if(st == ed) {
cout << 0 << endl;
return;
}
int res = -1;
while(!q1.empty() && !q2.empty()) {
// for(int i = 0; i < 4; i++) {
// cout << x[i] << ' ' << y[i] << endl;
// cout << endl;
// }
int cur_res;
if(q1.size() >= q2.size()) {
sta cur = q2.front();
q2.pop();
cur_res = bfs(cur, dis2, dis1, q2);
} else {
sta cur = q1.front();
q1.pop();
cur_res = bfs(cur, dis1, dis2, q1);
}
if(cur_res != -1) {
res = cur_res;
break;
}
}
cout << res << endl;
}
int main() {
cin >> t;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
while(t--) solve();
return 0;
}
created
last reply
- 1
reply
- 57
views
- 2
users
- 1
link