heisenberg0820

Untitled

Jun 21st, 2017
29
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define wt while(t--)
  4. #define fast ios_base::sync_with_stdio(false)
  5. #define pb push_back
  6. #define pob pop_back
  7. #define pf push_front
  8. #define pof pop_front
  9. #define mp make_pair
  10. #define MOD 1000000007
  11. #define EPS 1e-5
  12. #define INF (1<<28)
  13. #define pi 3.141593
  14. typedef unsigned long long int ull;
  15. typedef long long int ll;
  16.  
  17. using namespace std;
  18.  
  19. ll cell[2505][2505];
  20. ll dp[2505][2505];
  21. ll n,m;
  22.  
  23. bool isSafe(ll i,ll j)
  24. {
  25. if(i>0&&i<=n&&j>0&&j<=m)
  26. return true;
  27. return false;
  28. }
  29.  
  30. void markSafety(ll x,ll y,ll t,ll f)
  31. {
  32. ll tb,ts,i=0;
  33. for(i=0;isSafe(x+i,y);i++)
  34. {
  35. tb = t+i;
  36. ts = abs(x+i-1)+abs(y-1);
  37. if(ts>=tb&&(ts-tb)%f==0)
  38. cell[x+i][y] = 0;
  39. }
  40. for(i=0;isSafe(x-i,y);i++)
  41. {
  42. tb = t+i;
  43. ts = abs(x-i-1)+abs(y-1);
  44. if(ts>=tb&&(ts-tb)%f==0)
  45. cell[x-i][y] = 0;
  46. }
  47. for(i=0;isSafe(x,y+i);i++)
  48. {
  49. tb = t+i;
  50. ts = abs(x-1)+abs(y+i-1);
  51. if(ts>=tb&&(ts-tb)%f==0)
  52. cell[x][y+i] = 0;
  53. }
  54. for(i=0;isSafe(x,y-i);i++)
  55. {
  56. tb = t+i;
  57. ts = abs(x-1)+abs(y-i-1);
  58. if(ts>=tb&&(ts-tb)%f==0)
  59. cell[x][y-i] = 0;
  60. }
  61. }
  62.  
  63. void bfs(ll i,ll j)
  64. {
  65. ll x,y;
  66. queue<pair<ll,ll> >q;
  67. q.push(mp(i,j));
  68. pair<ll,ll> p;
  69. dp[i][j] = 0;
  70. while(!q.empty())
  71. {
  72. p = q.front();
  73. q.pop();
  74. x = p.first;
  75. y = p.second;
  76. if(isSafe(x+1,y))
  77. {
  78. if(dp[x+1][y]>dp[x][y]+1)
  79. {
  80. dp[x+1][y] = dp[x][y]+1;
  81. q.push(mp(x+1,y));
  82. }
  83. }
  84. if(isSafe(x,y+1))
  85. {
  86. if(dp[x][y+1]>dp[x][y]+1)
  87. {
  88. dp[x][y+1] = dp[x][y]+1;
  89. q.push(mp(x,y+1));
  90. }
  91. }
  92. }
  93. }
  94.  
  95. int main()
  96. {
  97. fast;
  98. ll k,i,x,y,t,f,ans,j;
  99. cin>>n>>m>>k;
  100. for(i=1;i<=n;i++)
  101. {
  102. for(j=1;j<=m;j++)
  103. {
  104. cell[i][j] = 1;
  105. dp[i][j] = 100000000;
  106. }
  107. }
  108. while(k--)
  109. {
  110. cin>>x>>y>>t>>f;
  111. markSafety(x,y,t,f);
  112. }
  113. if(cell[1][1]==1&&cell[n][m]==1)
  114. bfs(1,1);
  115. if(dp[n][m]!=100000000)
  116. {
  117. cout<<"YES\n";
  118. cout<<abs(n-1)+abs(m-1)<<"\n";
  119. }
  120. else
  121. cout<<"NO\n";
  122. return 0;
  123. }
Add Comment
Please, Sign In to add comment