Cod sursa(job #3261469)

Utilizator MagicantPlusIuoras Andrei MagicantPlus Data 6 decembrie 2024 08:52:09
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.83 kb
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define ull unsigned ll
#define vec vector
#define flist forward_list
#define um unordered_map
#define us unordered_set
#define prioq priority_queue
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ld long double
#define pll pair<ll, ll>
#define tll tuple<ll, ll, ll>
#define ass assign

#define LL_MAX LLONG_MAX
#define LL_MIN LLONG_MIN
#define ULL_MAX ULLONG_MAX
#define LD_MAX LDBL_MAX
#define LD_MIN LDBL_MIN

#define nl '\n'

#define vv(type, name, n, ...) vector<vector<type>> name(n, vector<type>(__VA_ARGS__))
#define vvv(type, name, n, m, ...)                                                                                     \
    vector<vector<vector<type>>> name(n, vector<vector<type>>(m, vector<type>(__VA_ARGS__)))

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rep1e(n) for(ll i=1; i<=(ll)(n); ++i)
#define rep2e(i,n) for(ll i=1; i<=(ll)(n); ++i)
#define rep3e(i,a,b) for(ll i=(ll)(a); i<=(ll)(b); ++i)
#define rep4e(i,a,b,c) for(ll i=(ll)(a); i<=(ll)(b); i+=(c))
#define repe(...) cut4(__VA_ARGS__,rep4e,rep3e,rep2e,rep1e)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define per1e(n) for(ll i=((ll)n); i>=1; --i)
#define per2e(i,n) for(ll i=((ll)n); i>=1; --i)
#define per3e(i,a,b) for(ll i=((ll)a); i>=(ll)(b); --i)
#define per4e(i,a,b,c) for(ll i=((ll)a); i>=(ll)(b); i-=(c))
#define pere(...) cut4(__VA_ARGS__,per4e,per3e,per2e,per1e)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
// #define forit(v) for (auto it = v.begin(); it != v.end(); it++)
// #define forit2(it, v) for (auto it = v.begin(); it != v.end(); it++)
// #define forrit(v) for (auto it = v.rbegin(); it != v.rend(); it++)
// #define forrit2(it, v) for (auto it = v.rbegin(); it != v.rend(); it++)

// #ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<vector<T>> x){cerr << "\n"; for(auto i: x) {for(auto j : i) {cerr << j << ' ';} cerr << "\n";}}
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
// #else
// #define bug(...) 777771449
// #endif

const ll MOD = 1e9 + 7;
const int INF = (1ll << 28);

const string FILENAME = "car";
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

#define cin fin
#define cout fout

ll dp[505][505][10];
bool inq[505][505][10], mat[505][505];
ll dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll n, m;

bool outOfBounds(ll i, ll j);

int main()
{
	rep(505) rep(j, 505) rep(d, 10) dp[i][j][d] = INF;
	ll si, sj, fi, fj;
	cin >> n >> m >> si >> sj >> fi >> fj;
	si--, sj--, fi--, fj--;
	
	rep(n)
	{
		rep(j, m)
		{
			bool val;
			cin >> val;
			mat[i][j] = val;
		}
	}
	
	queue<tll> nn;
	rep(8) dp[si][sj][i] = 0, inq[si][sj][i] = 1, nn.push({si, sj, i});
	
	while(!nn.empty())
	{
		ll x, y, d;
		tie(x, y, d) = nn.front();
		nn.pop();
		
		inq[x][y][d] = 0;
		
		
		repe(rot, 4)
		{
			if(dp[x][y][(d + rot) % 8] > dp[x][y][d] + rot)
			{
				dp[x][y][(d + rot) % 8] = dp[x][y][d] + rot;
				if(!inq[x][y][(d + rot) % 8])
				{
					inq[x][y][(d + rot) % 8] = 1;
					nn.push({x, y, (d + rot) % 8});
				}
			}
			
			if(dp[x][y][(d - rot + 8) % 8] > dp[x][y][d] + rot)
			{
				dp[x][y][(d - rot + 8) % 8] = dp[x][y][d] + rot;
				if(!inq[x][y][(d - rot + 8) % 8])
				{
					inq[x][y][(d - rot + 8) % 8] = 1;
					nn.push({x, y, (d - rot + 8) % 8});
				}
			}
		}
		
		if(!outOfBounds(x + dx[d], y + dy[d]))
		{
			if(dp[x + dx[d]][y + dy[d]][d] > dp[x][y][d])
			{
				dp[x + dx[d]][y + dy[d]][d] = dp[x][y][d];
				if(!inq[x + dx[d]][y + dy[d]][d])
				{
					inq[x + dx[d]][y + dy[d]][d] = 1;
					nn.push({x + dx[d], y + dy[d], d});
				}
			}
		}
	}
	
	ll ans = INF;
	rep(8) ans = min(ans, dp[fi][fj][i]);
	
	if(ans >= INF) cout << "-1";
	else cout << ans;
	
    return 0;
}

bool outOfBounds(ll i, ll j)
{
	if(0 <= i && i < n && 0 <= j && j < m && mat[i][j] == 0) return 0;
	return 1;
}