Advertisement
Guest User

Untitled

a guest
Jul 28th, 2016
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5.  
  6. const int N = (int) 5e2 + 123;
  7. const int INF = (int) 1e9 + 7;
  8.  
  9. char a[N][N];
  10. int x[2], y[2];
  11. int n, m;
  12. int dx[4] = {0, -1, 0, 1};
  13. int dy[4] = {1, 0, -1, 0};
  14. int dp[N][N];
  15. int path[N][N];
  16.  
  17. bool inBoard(int xx, int yy){
  18.     return xx >= 0 && yy >= 0 && xx < n && yy < m;
  19. }
  20.  
  21. int main() {
  22. #ifndef ONLINE_JUDGE
  23.     freopen("/Users/Hippskill/desktop/prog/cpp/input", "r", stdin);
  24. #endif
  25.     scanf("%d%d", &n, &m);
  26.     for(int i = 0; i < 2; i++){
  27.         scanf("%d %d", &x[i], &y[i]);
  28.         x[i]--; y[i]--;
  29.     }
  30.     for(int i = 0; i < n; i++){
  31.         for(int j = 0; j < m; j++){
  32.             dp[i][j] = INF;
  33.             path[i][j] = INF;
  34.         }
  35.         scanf("%s", a[i]);
  36.     }
  37.     vector<pair<int, int> > que;
  38.     dp[x[0]][y[0]] = 0;
  39.     que.push_back(make_pair(x[0], y[0]));
  40.     for(int i = 0; i < que.size(); i++){
  41.         pair<int, int> v = que[i];
  42.         for(int k = 0; k < 4; k++){
  43.             int xx = v.first + dx[k];
  44.             int yy = v.second + dy[k];
  45.             if(inBoard(xx, yy)){
  46.                 if(dp[xx][yy] > dp[v.first][v.second] + (a[xx][yy] != a[v.first][v.second])){
  47.                     dp[xx][yy] =  dp[v.first][v.second] + (a[xx][yy] != a[v.first][v.second]);
  48.                     que.push_back(make_pair(xx, yy));
  49.                 }
  50.             }
  51.         }
  52.     }
  53.     if(dp[x[1]][y[1]] == INF){
  54.         printf("0 0\n");
  55.         return 0;
  56.     }
  57.     else{
  58.         vector<pair<int, int> > q;
  59.         q.push_back(make_pair(x[0], y[0]));
  60.         path[x[0]][y[0]] = 0;
  61.         for(int i = 0; i < q.size(); i++){
  62.             pair<int, int> v = q[i];
  63.             for(int k = 0; k < 4; k++){
  64.                 int xx = v.first + dx[k];
  65.                 int yy = v.second + dy[k];
  66.                 printf("dp[%d][%d] = %d, dp[%d][%d] = %d\n", xx, yy, dp[xx][yy], v.first, v.second, dp[v.first][v.second]);
  67.                 if(inBoard(xx, yy) && (dp[xx][yy] == dp[v.first][v.second] + (a[xx][yy] == a[v.first][v.second]))){
  68.                     path[xx][yy] = min(path[xx][yy], path[v.first][v.second]+1);
  69.                     que.push_back(make_pair(xx, yy));
  70.                 }
  71.             }
  72.         }
  73.         printf("%d %d\n", path[ x[1] ][ y[1] ], dp[ x[1] ][ y[1] ]);
  74.     }
  75.  
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement