Advertisement
Guest User

Untitled

a guest
Mar 21st, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("ubuph.in");
  4. ofstream fout("ubuph.out");
  5. int n, m, matrix[100][100], dp[100][100], inx, iny, sfx, sfy;
  6. int dx[4] = {1, -1, 0, 0};
  7. int dy[4] = {0, 0, 1, -1};
  8. bool viz[100][100];
  9. queue <pair <int, int> > coada;
  10. void Citeste()
  11. {
  12. fin >> n >> m;
  13. for (int i = 1; i <= n; ++i)
  14. {
  15. for (int j = 1; j <= m; ++j)
  16. {
  17. fin >> matrix[i][j];
  18. dp[i][j] = 100000000;
  19. }
  20. }
  21. fin >> inx >> iny >> sfx >> sfy;
  22. }
  23. bool OK(int i, int j)
  24. {
  25. return i >= 1 && i <= n && j >= 1 && j <= m && viz[i][j] == 0;
  26. }
  27. int GetMin(int i, int j)
  28. {
  29. int minim = 100000000;
  30. for (int k = 0; k < 4; ++k)
  31. {
  32. int x = i + dx[k];
  33. int y = j + dy[k];
  34. if (dp[x][y] < minim)
  35. minim = dp[x][y];
  36. }
  37. return minim;
  38. }
  39. void Rezolva()
  40. {
  41. // bordare
  42. for (int j = 1; j <= m; ++j)
  43. dp[0][j] = dp[n + 1][j] = 100000000;
  44. for (int i = 1; i <= n; ++i)
  45. dp[i][0] = dp[i][m + 1] = 100000000;
  46. dp[inx][iny] = matrix[inx][iny];
  47. coada.push(make_pair(inx, iny));
  48. viz[inx][iny] = 1;
  49. while(!coada.empty())
  50. {
  51. int i = coada.front().first;
  52. int j = coada.front().second;
  53. coada.pop();
  54. for (int k = 0; k < 4; ++k)
  55. {
  56. int inew = i + dx[k];
  57. int jnew = j + dy[k];
  58. if (OK(inew, jnew))
  59. {
  60. coada.push(make_pair(inew, jnew));
  61. viz[inew][jnew] = 1;
  62. dp[inew][jnew] = matrix[inew][jnew];
  63. dp[inew][jnew] += GetMin(inew, jnew);
  64. }
  65. }
  66. }
  67. fout << dp[sfx][sfy];
  68. }
  69. int main()
  70. {
  71. Citeste();
  72. Rezolva();
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement