bfs40TLE求调
查看原帖
bfs40TLE求调
1272259
cgxd楼主2024/7/29 20:01
#include<bits/stdc++.h>
#define y1 yone
using namespace std;
int x1, y1, x2, y2;
unordered_map<int, unordered_set<int>> vis;
deque<tuple<int, int, int>> dq;
const tuple<int, int, int> dir[]{{1, 2, 1}, {1, -2, 1}, {-1, 2, 1}, {-1, -2, 1}, {2, 1, 1}, {-2, 1, 1}, {2, -1, 1}, {-2, -1, 1}};
tuple<int, int, int> operator+=(tuple<int, int, int> &t1, tuple<int, int, int> t2){
	get<0>(t1) += get<0>(t2);
	get<1>(t1) += get<1>(t2);
	get<2>(t1) += get<2>(t2);
	return t1;
}signed main(){
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	dq.push_back(tuple<int, int, int>(x1, y1, 0));
	vis[x1].insert(y1);
	while(dq.size()){
		tuple<int, int, int> t = dq[0];
		dq.pop_front();
		for(tuple<int, int, int> t1: dir){
			t1 += t;
			int x = get<0>(t1), y = get<1>(t1), st = get<2>(t1);
			if(vis[x].count(y))
				continue;
			vis[x].insert(y);
			dq.push_back(t1);
			if(x == x2 and y == y2){
				printf("%d", st);
				return 0;
			}
		}
	}return 0;
}
2024/7/29 20:01
加载中...