Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define wt while(t--)
- #define fast ios_base::sync_with_stdio(false)
- #define pb push_back
- #define pob pop_back
- #define pf push_front
- #define pof pop_front
- #define mp make_pair
- #define MOD 1000000007
- #define EPS 1e-5
- #define INF (1<<28)
- #define pi 3.141593
- typedef unsigned long long int ull;
- typedef long long int ll;
- using namespace std;
- ll cell[2505][2505];
- ll dp[2505][2505];
- ll n,m;
- bool isSafe(ll i,ll j)
- {
- if(i>0&&i<=n&&j>0&&j<=m)
- return true;
- return false;
- }
- void markSafety(ll x,ll y,ll t,ll f)
- {
- ll tb,ts,i=0;
- for(i=0;isSafe(x+i,y);i++)
- {
- tb = t+i;
- ts = abs(x+i-1)+abs(y-1);
- if(ts>=tb&&(ts-tb)%f==0)
- cell[x+i][y] = 0;
- }
- for(i=0;isSafe(x-i,y);i++)
- {
- tb = t+i;
- ts = abs(x-i-1)+abs(y-1);
- if(ts>=tb&&(ts-tb)%f==0)
- cell[x-i][y] = 0;
- }
- for(i=0;isSafe(x,y+i);i++)
- {
- tb = t+i;
- ts = abs(x-1)+abs(y+i-1);
- if(ts>=tb&&(ts-tb)%f==0)
- cell[x][y+i] = 0;
- }
- for(i=0;isSafe(x,y-i);i++)
- {
- tb = t+i;
- ts = abs(x-1)+abs(y-i-1);
- if(ts>=tb&&(ts-tb)%f==0)
- cell[x][y-i] = 0;
- }
- }
- void bfs(ll i,ll j)
- {
- ll x,y;
- queue<pair<ll,ll> >q;
- q.push(mp(i,j));
- pair<ll,ll> p;
- dp[i][j] = 0;
- while(!q.empty())
- {
- p = q.front();
- q.pop();
- x = p.first;
- y = p.second;
- if(isSafe(x+1,y))
- {
- if(dp[x+1][y]>dp[x][y]+1)
- {
- dp[x+1][y] = dp[x][y]+1;
- q.push(mp(x+1,y));
- }
- }
- if(isSafe(x,y+1))
- {
- if(dp[x][y+1]>dp[x][y]+1)
- {
- dp[x][y+1] = dp[x][y]+1;
- q.push(mp(x,y+1));
- }
- }
- }
- }
- int main()
- {
- fast;
- ll k,i,x,y,t,f,ans,j;
- cin>>n>>m>>k;
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=m;j++)
- {
- cell[i][j] = 1;
- dp[i][j] = 100000000;
- }
- }
- while(k--)
- {
- cin>>x>>y>>t>>f;
- markSafety(x,y,t,f);
- }
- if(cell[1][1]==1&&cell[n][m]==1)
- bfs(1,1);
- if(dp[n][m]!=100000000)
- {
- cout<<"YES\n";
- cout<<abs(n-1)+abs(m-1)<<"\n";
- }
- else
- cout<<"NO\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment