daily pastebin goal
24%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <queue>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. typedef std::vector<std::vector<unsigned int>> Matrix;
  6.  
  7. struct Cell {
  8.     unsigned int x;
  9.     unsigned int y;
  10.     unsigned long long weight;
  11.    
  12.     Cell(unsigned int x_, unsigned int y_, unsigned long long weight_) : x(x_), y(y_), weight(weight_) {}
  13.    
  14.     bool operator<(const Cell& cell) const {
  15.         return weight > cell.weight;
  16.     }
  17. };
  18.  
  19. unsigned long long search(const Matrix& matrix) {
  20.     const auto size = matrix.size();
  21.     std::vector<std::vector<bool>> processed(matrix.size());
  22.     for(auto& row : processed) {
  23.         row.resize(size, false);
  24.     }
  25.     std::priority_queue<Cell> next;
  26.     next.push(Cell(0, 0, matrix[0][0]));
  27.     while(!next.empty()) {
  28.         Cell cell = next.top();
  29.         next.pop();
  30.         if(!processed[cell.y][cell.x]) {
  31.             processed[cell.y][cell.x] = true;
  32.             if(cell.x == size - 1 && cell.y == size - 1) {
  33.                 return cell.weight;
  34.             }
  35.             if(cell.x + 1 < size) {
  36.                 next.push(Cell(cell.x + 1, cell.y, cell.weight + matrix[cell.y][cell.x + 1]));
  37.             }
  38.             if(cell.y + 1 < size) {
  39.                 next.push(Cell(cell.x, cell.y + 1, cell.weight + matrix[cell.y + 1][cell.x]));
  40.             }
  41.             if(cell.y > 0) {
  42.                 next.push(Cell(cell.x, cell.y - 1, cell.weight + matrix[cell.y - 1][cell.x]));
  43.             }
  44.             if(cell.x > 0) {
  45.                 next.push(Cell(cell.x - 1, cell.y, cell.weight + matrix[cell.y][cell.x - 1]));
  46.             }
  47.         }
  48.     }
  49.     return -1;
  50. }
  51.  
  52. int main() {
  53.     unsigned int N;
  54.     std::cin >> N;
  55.    
  56.     Matrix matrix(N);
  57.     for(auto& row : matrix) {
  58.         row.resize(N);
  59.         for(auto& cell : row) {
  60.             std::cin >> cell;
  61.         }
  62.     }
  63.     std::cout << search(matrix) << std::endl;
  64.     return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top