Advertisement
Josif_tepe

Untitled

Nov 27th, 2021
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. vector<pair<int,int>> findourv;
  8. int a,b;
  9. char mat[55][55];
  10.  
  11. int bfs(vector<pair<int,int>> v, map<vector<pair<int,int>>, bool>pos, char c)
  12. {
  13.     //toa sto dvizime piano
  14.     queue<vector<pair<int,int>>>Q;
  15.     Q.push(v);
  16.     //cekori
  17.     queue<int>q;
  18.     q.push(0);
  19.     while(!q.empty())
  20.     {
  21.        vector<pair<int,int>> vi=Q.front();
  22.        Q.pop();
  23.        int k=q.front();
  24.        q.pop();
  25.        if(vi==findourv)
  26.        {
  27.            return k;
  28.        }
  29.        bool t=true;
  30.        for(int i=0;i<vi.size();i++)
  31.        {
  32.            if(vi[i].first + 1>=a)
  33.            {
  34.               t=false;
  35.               break;
  36.            }
  37.            if(mat[vi[i].first +1][vi[i].second]=='#')
  38.            {
  39.               t=false;
  40.               break;
  41.            }
  42.            if(isdigit(mat[vi[i].first +1][vi[i].second]) && mat[vi[i].first +1][vi[i].second]!=c)
  43.            {
  44.                t=false;
  45.                break;
  46.            }
  47.        }
  48.        if(t==true)
  49.        {
  50.            vector<pair<int,int>> nadole;
  51.            nadole=vi;
  52.            for(int i=0;i<nadole.size();i++)
  53.            {
  54.                nadole[i].first+=1;
  55.            }
  56.            if(pos[nadole]==false)
  57.            {
  58.                pos[nadole]=true;
  59.                Q.push(nadole);
  60.                q.push(k+1);
  61.            }
  62.        }
  63.        t=true;
  64.        for(int i=0;i<vi.size();i++)
  65.        {
  66.            if(vi[i].first - 1<0)
  67.            {
  68.                t=false;
  69.                break;
  70.            }
  71.            if(mat[vi[i].first - 1][vi[i].second]=='#')
  72.            {
  73.                t=false;
  74.                break;
  75.            }
  76.            if(isdigit(mat[vi[i].first - 1][vi[i].second]) && mat[vi[i].first - 1][vi[i].second]!=c)
  77.            {
  78.                t=false;
  79.                break;
  80.            }
  81.        }
  82.        if(t==true)
  83.        {
  84.            vector<pair<int,int>>najgore;
  85.            najgore=vi;
  86.            for(int i=0;i<najgore.size();i++)
  87.            {
  88.                najgore[i].first-=1;
  89.            }
  90.            if(pos[najgore]!=true)
  91.            {
  92.                pos[najgore]=true;
  93.                Q.push(najgore);
  94.                q.push(k+1);
  95.            }
  96.        }
  97.        t=true;
  98.        for(int i=0;i<vi.size();i++)
  99.        {
  100.            if(vi[i].second + 1>=b)
  101.            {
  102.               t=false;
  103.               break;
  104.            }
  105.            if(mat[vi[i].first][vi[i].second + 1]=='#')
  106.            {
  107.               t=false;
  108.               break;
  109.            }
  110.            if(isdigit(mat[vi[i].first][vi[i].second + 1]) && mat[vi[i].first][vi[i].second + 1]!=c)
  111.            {
  112.                t=false;
  113.                break;
  114.            }
  115.        }
  116.        if(t==true)
  117.        {
  118.            vector<pair<int,int>> desno;
  119.            desno=vi;
  120.            for(int i=0;i<desno.size();i++)
  121.            {
  122.                desno[i].second+=1;
  123.            }
  124.            if(pos[desno]==false)
  125.            {
  126.                pos[desno]=true;
  127.                Q.push(desno);
  128.                q.push(k+1);
  129.            }
  130.        }
  131.        t=true;
  132.        for(int i=0;i<vi.size();i++)
  133.        {
  134.            if(vi[i].second - 1<0)
  135.            {
  136.               t=false;
  137.               break;
  138.            }
  139.            if(mat[vi[i].first][vi[i].second - 1]=='#')
  140.            {
  141.               t=false;
  142.               break;
  143.            }
  144.            if(isdigit(mat[vi[i].first][vi[i].second - 1]) && mat[vi[i].first][vi[i].second - 1]!=c)
  145.            {
  146.                t=false;
  147.                break;
  148.            }
  149.        }
  150.        if(t==true)
  151.        {
  152.            vector<pair<int,int>> levo;
  153.            levo=vi;
  154.            for(int i=0;i<levo.size();i++)
  155.            {
  156.                levo[i].second-=1;
  157.            }
  158.            if(pos[levo]==false)
  159.            {
  160.                pos[levo]=true;
  161.                Q.push(levo);
  162.                q.push(k+1);
  163.            }
  164.        }
  165.     }
  166.     return 1000000;
  167. }
  168.  
  169. int main()
  170. {
  171.     cin>>b>>a;
  172.     vector<pair<int,int>>v1;
  173.     vector<pair<int,int>>v2;
  174.     vector<pair<int,int>>v3;
  175.     map<vector<pair<int,int>>,bool> pos;
  176.     for(int i=0;i<a;i++)
  177.     {
  178.         for(int j=0;j<b;j++)
  179.         {
  180.             cin>>mat[i][j];
  181.             if(mat[i][j]=='1')
  182.             {
  183.                 v1.push_back(make_pair(i,j));
  184.             }
  185.             if(mat[i][j]=='2')
  186.             {
  187.                 v2.push_back(make_pair(i,j));
  188.             }
  189.             if(mat[i][j]=='3')
  190.             {
  191.                 v3.push_back(make_pair(i,j));
  192.             }
  193.             if(mat[i][j]=='F')
  194.             {
  195.                 findourv.push_back(make_pair(i,j));
  196.             }
  197.         }
  198.     }
  199.     pos[v1]=true;
  200.     int p1=bfs(v1,pos,'1');
  201.     pos.clear();
  202.     pos[v2]=true;
  203.     int p2=bfs(v2,pos,'2');
  204.     pos.clear();
  205.     pos[v3]=true;
  206.     int p3=bfs(v3,pos,'3');
  207.     int najmal=1000000;
  208.     if(p1<najmal)
  209.     {
  210.         najmal=p1;
  211.     }
  212.     if(p2<najmal)
  213.     {
  214.         najmal=p2;
  215.     }
  216.     if(p3<najmal)
  217.     {
  218.         najmal=p3;
  219.     }
  220.     if(najmal == p1) {
  221.         cout << 1 << endl;
  222.     }
  223.     else if(najmal == p2) {
  224.         cout << 2 << endl;
  225.     }
  226.     else {
  227.         cout << 3 << endl;
  228.     }
  229.     cout << najmal << endl;
  230.    
  231.     return 0;
  232. }
  233.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement