Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <queue>
- #include <map>
- using namespace std;
- struct state
- {
- int x;
- int y;
- int b;
- state(int xx, int yy, int bb)
- {
- x = xx;
- y = yy;
- b = bb;
- }
- };
- int xd[] = {0,0,1,-1};
- int yd[] = {1,-1,0,0};
- bool visited[50][50][100];
- int dist[50][50][100];
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n, bombs;
- cin>>n;
- string mapa[n];
- pair<int, int> start;
- pair<int, int> finish;
- for(int i = 0 ; i < n ; ++i)
- {
- cin>>mapa[i];
- for(int j = 0 ; j < mapa[0].size() ; ++j)
- {
- if(mapa[i][j] == 'B')
- start = make_pair(i,j);
- else if(mapa[i][j] == 'E')
- finish = make_pair(i,j);
- }
- }
- cin>>bombs;
- visited[start.first][start.second][0] = true;
- queue<state> Q;
- Q.push(state(start.first,start.second,0));
- while(!Q.empty())
- {
- state curr = Q.front();
- Q.pop();
- if(curr.x == finish.first && curr.y == finish.second)
- {
- dist[curr.x][curr.y][curr.b];
- return 0;
- }
- for(int i = 0 ; i < 4 ; ++i)
- {
- int x = curr.x + xd[i];
- int y = curr.y + yd[i];
- if(x >= 0 && x < n && y >= 0 && y < mapa[0].size())
- {
- if(mapa[x][y] == '#' && curr.b < bombs && !visited[x][y][curr.b+1])
- {
- dist[x][y][curr.b+1] = dist[curr.x][curr.y][curr.b] + 3;
- Q.push(state(x,y,curr.b+1));
- visited[x][y][curr.b+1] = true;
- }
- else if(mapa[x][y] != '#' && !visited[x][y][curr.b])
- {
- dist[x][y][curr.b] = dist[curr.x][curr.y][curr.b] + 1;
- Q.push(state(x,y,curr.b));
- visited[x][y][curr.b] = true;
- }
- }
- }
- }
- cout<<-1;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement