Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <map>
- using namespace std;
- int n, m;
- char mat[55][55];
- int bfs(vector<pair<int, int>> p, vector<pair<int, int>> F, char c) {
- queue<vector<pair<int, int>>> q;
- q.push(p);
- queue<int> q_dist;
- q_dist.push(0);
- map<vector<pair<int, int>>, bool> visited;
- int di[] = {-1, 1, 0, 0};
- int dj[] = {0, 0, -1, 1};
- while(!q.empty()) {
- vector<pair<int, int>> piano = q.front();
- q.pop();
- int dist = q_dist.front();
- q_dist.pop();
- if(piano == F) {
- return dist;
- }
- for(int k = 0; k < 4; k++) {
- vector<pair<int, int>> t_piano = piano;
- bool ok = true;
- for(int i = 0; i < t_piano.size(); i++) {
- t_piano[i].first += di[k];
- t_piano[i].second += dj[k];
- if(t_piano[i].first < 0 or t_piano[i].first >= n or t_piano[i].second < 0 or t_piano[i].second >= m) {
- ok = false;
- break;
- }
- if(mat[t_piano[i].first][t_piano[i].second] == '#') {
- ok = false;
- break;
- }
- if(mat[t_piano[i].first][t_piano[i].second] >= '1' and mat[t_piano[i].first][t_piano[i].second] <= '3') {
- if(mat[t_piano[i].first][t_piano[i].second] != c) {
- ok = false;
- break;
- }
- }
- }
- if(ok and !visited[t_piano]) {
- visited[t_piano] = true;
- q.push(t_piano);
- q_dist.push(dist + 1);
- }
- }
- }
- return 2e9;
- }
- int main() {
- cin >> m >> n;
- vector<pair<int, int>> F;
- vector<pair<int, int>> one, two, three;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cin >> mat[i][j];
- if(mat[i][j] == 'F') {
- F.push_back(make_pair(i, j));
- }
- if(mat[i][j] == '1') {
- one.push_back(make_pair(i, j));
- }
- if(mat[i][j] == '2') {
- two.push_back(make_pair(i, j));
- }
- if(mat[i][j] == '3') {
- three.push_back(make_pair(i, j));
- }
- }
- }
- int o = bfs(one, F, '1');
- int t = bfs(two, F, '2');
- int th = bfs(three, F, '3');
- int res = min(o, min(t, th));
- if(res == o) {
- cout << 1 << endl << res << endl;
- }
- else if(res == t) {
- cout << 2 << endl << res << endl;
- }
- else {
- cout << 3 << endl << res << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement