Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <queue>
- #include <utility>
- #include <vector>
- using namespace std;
- ifstream in("input.txt");
- ofstream out("output.txt");
- struct nodo{
- int r;
- int c;
- int dist;
- nodo(int r, int c, int dist) : r(r), c(c), dist(dist) {}
- };
- typedef pair<int,int> point;
- main(){
- int H, W;
- in>>H>>W;
- char grid[H][W];
- bool vis[H][W];
- int rc, cc;
- vector <point> tp;
- int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
- for(int i = 0; i < H; i++){
- for(int j = 0; j < W; j++){
- in>>grid[i][j];
- vis[i][j] = false;
- if(grid[i][j] == 'C'){
- rc = i;
- cc = j;
- }
- else if(grid[i][j] == '@'){
- point app;
- app.first = i;
- app.second = j;
- tp.push_back(app);
- }
- }
- }
- queue<nodo> q;
- q.push(nodo(rc,cc,0));
- while(!q.empty()){
- nodo cur = q.front();
- q.pop();
- if(vis[cur.r][cur.c] == true){
- continue;
- }
- vis[cur.r][cur.c] = true;
- if(grid[cur.r][cur.c] == 'M'){
- out<<cur.dist;
- break;
- }
- for(int i = 0; i < 4; i++){
- int nr = cur.r + dir[i][0];
- int nc = cur.c + dir[i][1];
- if(nr >= 0 && nr < H && nc >= 0 && nc < W && vis[nr][nc] == false && grid[nr][nc] != '#'){
- q.push(nodo(nr,nc,cur.dist + 1));
- }
- }
- if(grid[cur.r][cur.c] == '@'){
- for(int i = 0; i < tp.size(); i++){
- point app = tp[i];
- if(app.first != cur.r && app.second != cur.c){
- if(vis[app.first][app.second] == false){
- q.push(nodo(app.first, app.second, cur.dist + 1));
- }
- }
- }
- }
- //cout<<cur.r<<" "<<cur.c<<" "<<grid[cur.r][cur.c]<<" "<<cur.dist<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement