Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("ubuph.in");
- ofstream fout("ubuph.out");
- int n, m, matrix[100][100], dp[100][100], inx, iny, sfx, sfy;
- int dx[4] = {1, -1, 0, 0};
- int dy[4] = {0, 0, 1, -1};
- bool viz[100][100];
- queue <pair <int, int> > coada;
- void Citeste()
- {
- fin >> n >> m;
- for (int i = 1; i <= n; ++i)
- {
- for (int j = 1; j <= m; ++j)
- {
- fin >> matrix[i][j];
- dp[i][j] = 100000000;
- }
- }
- fin >> inx >> iny >> sfx >> sfy;
- }
- bool OK(int i, int j)
- {
- return i >= 1 && i <= n && j >= 1 && j <= m && viz[i][j] == 0;
- }
- int GetMin(int i, int j)
- {
- int minim = 100000000;
- for (int k = 0; k < 4; ++k)
- {
- int x = i + dx[k];
- int y = j + dy[k];
- if (dp[x][y] < minim)
- minim = dp[x][y];
- }
- return minim;
- }
- void Rezolva()
- {
- // bordare
- for (int j = 1; j <= m; ++j)
- dp[0][j] = dp[n + 1][j] = 100000000;
- for (int i = 1; i <= n; ++i)
- dp[i][0] = dp[i][m + 1] = 100000000;
- dp[inx][iny] = matrix[inx][iny];
- coada.push(make_pair(inx, iny));
- viz[inx][iny] = 1;
- while(!coada.empty())
- {
- int i = coada.front().first;
- int j = coada.front().second;
- coada.pop();
- for (int k = 0; k < 4; ++k)
- {
- int inew = i + dx[k];
- int jnew = j + dy[k];
- if (OK(inew, jnew))
- {
- coada.push(make_pair(inew, jnew));
- viz[inew][jnew] = 1;
- dp[inew][jnew] = matrix[inew][jnew];
- dp[inew][jnew] += GetMin(inew, jnew);
- }
- }
- }
- fout << dp[sfx][sfy];
- }
- int main()
- {
- Citeste();
- Rezolva();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement