Advertisement
ismaeil

Algo Project 2

Jul 23rd, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> ii;
  5. #define OO 0x7fffffff
  6. #define S second
  7. #define F first
  8.  
  9. int dx[] = {1 ,-1 ,0 , 0};
  10. int dy[] = {0 , 0 ,1 ,-1};
  11. const int N = 1e3 + 3e1;
  12.  
  13. vector< vector< ii > > kColorIdx;
  14. int Grid[N][N];
  15. int n ,m ,k;
  16.  
  17. inline bool isValid(int i ,int j) {
  18.     return (i > 0 && j > 0 && i <= n && j <= m && Grid[i][j] != 0);
  19. }
  20.  
  21. int BFS( ii Start , ii End ) {
  22.         vector< vector<int> > Dist(n + 1 , vector<int>(m + 1 ,OO) );
  23.         Dist[ Start.F ][ Start.S ] = 0;
  24.         queue< ii > Q; Q.push( Start );
  25.  
  26.         while( !Q.empty() ) {
  27.                 ii front = Q.front(); Q.pop();
  28.  
  29.                 int i = front.F , j = front.S;
  30.                 int Color = Grid[i][j];
  31.                 for(int x = 0 ; x < (int)kColorIdx[ Color ].size() ; x++) {
  32.                         ii idx = kColorIdx[ Color ][ x ];
  33.                         Dist[ idx.F ][ idx.S ] = Dist[i][j];
  34.  
  35.                         for(int move = 0 ; move < 4 ; move ++) {
  36.                                 int newI = idx.F + dx[ move ];
  37.                                 int newJ = idx.S + dy[ move ];
  38.  
  39.                                 if( isValid(newI ,newJ) && Dist[ newI ][ newJ ] == OO && Grid[ newI ][ newJ ] != Color ) {
  40.                                         Dist[ newI ][ newJ ] = Dist[ idx.F ][ idx.S ] + 1;
  41.                                         Q.push( ii(newI ,newJ) );
  42.                                 }
  43.                         }
  44.                 }
  45.         }
  46.  
  47.         return Dist[ End.F ][ End.S ];
  48. }
  49.  
  50. int main()
  51. {
  52.     scanf("%d%d%d" ,&n ,&m ,&k);
  53.     kColorIdx.assign(k + 1 ,vector<ii>());
  54.  
  55.     ii stIdx = ii(0 ,0) ,edIdx = ii(0 ,0);
  56.     for(int i = 1 ; i <= n ; i++){
  57.         for(int j = 1 ; j <= m ; j++){
  58.             scanf("%d" ,&Grid[i][j]);
  59.             int Color = Grid[i][j];
  60.  
  61.             kColorIdx[ Color ].push_back( ii(i ,j) );
  62.  
  63.             if( Color == 1 ) stIdx = ii(i ,j);
  64.             if( Color == k ) edIdx = ii(i ,j);
  65.         }
  66.     }
  67.  
  68.     printf( "%d" ,BFS(stIdx ,edIdx) );
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement