Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <queue>
- using namespace std;
- vector<pair<int,int>> findourv;
- int a,b;
- char mat[55][55];
- int bfs(vector<pair<int,int>> v, map<vector<pair<int,int>>, bool>pos, char c)
- {
- //toa sto dvizime piano
- queue<vector<pair<int,int>>>Q;
- Q.push(v);
- //cekori
- queue<int>q;
- q.push(0);
- while(!q.empty())
- {
- vector<pair<int,int>> vi=Q.front();
- Q.pop();
- int k=q.front();
- q.pop();
- if(vi==findourv)
- {
- return k;
- }
- bool t=true;
- for(int i=0;i<vi.size();i++)
- {
- if(vi[i].first + 1>=a)
- {
- t=false;
- break;
- }
- if(mat[vi[i].first +1][vi[i].second]=='#')
- {
- t=false;
- break;
- }
- if(isdigit(mat[vi[i].first +1][vi[i].second]) && mat[vi[i].first +1][vi[i].second]!=c)
- {
- t=false;
- break;
- }
- }
- if(t==true)
- {
- vector<pair<int,int>> nadole;
- nadole=vi;
- for(int i=0;i<nadole.size();i++)
- {
- nadole[i].first+=1;
- }
- if(pos[nadole]==false)
- {
- pos[nadole]=true;
- Q.push(nadole);
- q.push(k+1);
- }
- }
- t=true;
- for(int i=0;i<vi.size();i++)
- {
- if(vi[i].first - 1<0)
- {
- t=false;
- break;
- }
- if(mat[vi[i].first - 1][vi[i].second]=='#')
- {
- t=false;
- break;
- }
- if(isdigit(mat[vi[i].first - 1][vi[i].second]) && mat[vi[i].first - 1][vi[i].second]!=c)
- {
- t=false;
- break;
- }
- }
- if(t==true)
- {
- vector<pair<int,int>>najgore;
- najgore=vi;
- for(int i=0;i<najgore.size();i++)
- {
- najgore[i].first-=1;
- }
- if(pos[najgore]!=true)
- {
- pos[najgore]=true;
- Q.push(najgore);
- q.push(k+1);
- }
- }
- t=true;
- for(int i=0;i<vi.size();i++)
- {
- if(vi[i].second + 1>=b)
- {
- t=false;
- break;
- }
- if(mat[vi[i].first][vi[i].second + 1]=='#')
- {
- t=false;
- break;
- }
- if(isdigit(mat[vi[i].first][vi[i].second + 1]) && mat[vi[i].first][vi[i].second + 1]!=c)
- {
- t=false;
- break;
- }
- }
- if(t==true)
- {
- vector<pair<int,int>> desno;
- desno=vi;
- for(int i=0;i<desno.size();i++)
- {
- desno[i].second+=1;
- }
- if(pos[desno]==false)
- {
- pos[desno]=true;
- Q.push(desno);
- q.push(k+1);
- }
- }
- t=true;
- for(int i=0;i<vi.size();i++)
- {
- if(vi[i].second - 1<0)
- {
- t=false;
- break;
- }
- if(mat[vi[i].first][vi[i].second - 1]=='#')
- {
- t=false;
- break;
- }
- if(isdigit(mat[vi[i].first][vi[i].second - 1]) && mat[vi[i].first][vi[i].second - 1]!=c)
- {
- t=false;
- break;
- }
- }
- if(t==true)
- {
- vector<pair<int,int>> levo;
- levo=vi;
- for(int i=0;i<levo.size();i++)
- {
- levo[i].second-=1;
- }
- if(pos[levo]==false)
- {
- pos[levo]=true;
- Q.push(levo);
- q.push(k+1);
- }
- }
- }
- return 1000000;
- }
- int main()
- {
- cin>>b>>a;
- vector<pair<int,int>>v1;
- vector<pair<int,int>>v2;
- vector<pair<int,int>>v3;
- map<vector<pair<int,int>>,bool> pos;
- for(int i=0;i<a;i++)
- {
- for(int j=0;j<b;j++)
- {
- cin>>mat[i][j];
- if(mat[i][j]=='1')
- {
- v1.push_back(make_pair(i,j));
- }
- if(mat[i][j]=='2')
- {
- v2.push_back(make_pair(i,j));
- }
- if(mat[i][j]=='3')
- {
- v3.push_back(make_pair(i,j));
- }
- if(mat[i][j]=='F')
- {
- findourv.push_back(make_pair(i,j));
- }
- }
- }
- pos[v1]=true;
- int p1=bfs(v1,pos,'1');
- pos.clear();
- pos[v2]=true;
- int p2=bfs(v2,pos,'2');
- pos.clear();
- pos[v3]=true;
- int p3=bfs(v3,pos,'3');
- int najmal=1000000;
- if(p1<najmal)
- {
- najmal=p1;
- }
- if(p2<najmal)
- {
- najmal=p2;
- }
- if(p3<najmal)
- {
- najmal=p3;
- }
- if(najmal == p1) {
- cout << 1 << endl;
- }
- else if(najmal == p2) {
- cout << 2 << endl;
- }
- else {
- cout << 3 << endl;
- }
- cout << najmal << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement