Advertisement
Guest User

Untitled

a guest
Jan 20th, 2017
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. #include <utility>
  5. #include <vector>
  6. using namespace std;
  7. ifstream in("input.txt");
  8. ofstream out("output.txt");
  9.  
  10. struct nodo{
  11.     int r;
  12.     int c;
  13.     int dist;
  14.    
  15.     nodo(int r, int c, int dist) : r(r), c(c), dist(dist) {}
  16. };
  17.  
  18. typedef pair<int,int> point;
  19.  
  20. main(){
  21.     int H, W;
  22.     in>>H>>W;
  23.     char grid[H][W];
  24.     bool vis[H][W];
  25.     int rc, cc;
  26.     vector <point> tp;
  27.     int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
  28.    
  29.     for(int i = 0; i < H; i++){
  30.         for(int j = 0; j < W; j++){
  31.             in>>grid[i][j];
  32.             vis[i][j] = false;
  33.             if(grid[i][j] == 'C'){
  34.                 rc = i;
  35.                 cc = j;
  36.             }
  37.             else if(grid[i][j] == '@'){
  38.                 point app;
  39.                 app.first = i;
  40.                 app.second = j;
  41.                 tp.push_back(app);
  42.             }
  43.         }
  44.     }
  45.  
  46.     queue<nodo> q;
  47.     q.push(nodo(rc,cc,0));
  48.    
  49.     while(!q.empty()){
  50.         nodo cur = q.front();
  51.         q.pop();
  52.        
  53.         if(vis[cur.r][cur.c] == true){
  54.             continue;
  55.         }
  56.        
  57.         vis[cur.r][cur.c] = true;
  58.        
  59.         if(grid[cur.r][cur.c] == 'M'){
  60.             out<<cur.dist;
  61.             break;
  62.         }
  63.        
  64.         for(int i = 0; i < 4; i++){
  65.             int nr = cur.r + dir[i][0];
  66.             int nc = cur.c + dir[i][1];
  67.             if(nr >= 0 && nr < H && nc >= 0 && nc < W && vis[nr][nc] == false && grid[nr][nc] != '#'){
  68.                 q.push(nodo(nr,nc,cur.dist + 1));
  69.             }
  70.         }
  71.        
  72.         if(grid[cur.r][cur.c] == '@'){
  73.             for(int i = 0; i < tp.size(); i++){
  74.                 point app = tp[i];
  75.                 if(app.first != cur.r && app.second != cur.c){
  76.                     if(vis[app.first][app.second] == false){
  77.                         q.push(nodo(app.first, app.second, cur.dist + 1));
  78.                     }
  79.                 }
  80.             }
  81.         }
  82.         //cout<<cur.r<<" "<<cur.c<<" "<<grid[cur.r][cur.c]<<" "<<cur.dist<<endl;
  83.        
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement