DFS TLE蒟蒻投降
查看原帖
DFS TLE蒟蒻投降
1392551
ruo_aqueous楼主2025/1/5 19:12
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define ll long long
#define for1(i,a,b) for(long long i = (long long) (a);i <= (long long) (b);++ i)
#define for0(i,a,b) for(long long i = (long long) (a);i >= (long long) (b);-- i)
#define lb (ll)bool
struct st{ll x, y, step;};
stack <st> a;
ll zx[8] = {-1, -1, -2, -2, 1, 1, 2, 2};
ll zy[8] = {-2, 2, -1, 1, -2, 2, -1, 1};
ll cx, cy, step, nx, ny, dx, dy, x, y;
short jyh[410][410];
void bfs (){
	a.push (st {x, y, step});
	while (!a.empty()){
		x = a.top().x, y = a.top().y, step = a.top().step+1;
		a.pop ();
		for1 (i, 0, 7){
			nx = x+zx[i], ny = y+zy[i];
			if (min(nx,ny)<1||nx>dx||ny>dy||step>=jyh[nx][ny]&&jyh[nx][ny]) continue;
			a.push (st {nx, ny, step}), jyh[nx][ny] = step;
		}
	}
}
int main(){
	ios::sync_with_stdio (0);cin.tie (0);cout.tie (0);
	cin >>dx >>dy >>cx >>cy;
	x = cx, y = cy;
	bfs ();
	for1 (i, 1, dx){
		for1 (j, 1, dy){
			if (i == cx && j == cy)		cout <<0;
			else if (jyh[i][j] == 0)	cout <<-1;
			else						cout <<jyh[i][j];
			cout <<setw (4);
		}
		cout <<'\n';
	}
	return 0;
}
2025/1/5 19:12
加载中...