Advertisement
ivangarvanliev

Untitled

Jan 17th, 2025
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <queue>
  5. #define x first
  6. #define y second
  7. using namespace std;
  8. char C[55][55];
  9. int N,M;
  10. pair<int,int> st[15];
  11. pair<int,int> dr[15];
  12. int dist[55][55];
  13. int dx[]={-1,0,1,0};
  14. int dy[]={0,1,0,-1};
  15. int rez=1<<30,ind;
  16. int main()
  17. {
  18.     scanf("%d %d\n",&M,&N);
  19.     for(int i=1;i<=N;i++)
  20.         fgets(C[i]+1,55,stdin);
  21.     for(int i=1;i<=N;i++)
  22.     {
  23.         for(int j=1;j<=M;j++)
  24.         {
  25.             if(C[i][j]=='.'||C[i][j]=='#')continue;
  26.             if(C[i][j]=='F')
  27.             {
  28.                 if(!st[4].x)st[4]={i,j};
  29.                 dr[4]={i,j};
  30.             }
  31.             if(!st[C[i][j]-'0'].x)st[C[i][j]-'0']={i,j};
  32.             dr[C[i][j]-'0']={i,j};
  33.         }
  34.     }
  35.     for(int i=1;i<=N;i++)
  36.     {
  37.         for(int j=1;j<=M;j++)
  38.         {
  39.             if(C[i][j]=='#')
  40.             {
  41.                 for(int k=i;k&&k>i-(dr[1].x-st[1].x+1);k--)
  42.                     for(int l=j;l&&l>j-(dr[1].y-st[1].y+1);l--)
  43.                         C[k][l]='#';
  44.             }
  45.         }
  46.     }
  47.     //for(int i=1;i<=N;i++)printf("%s\n",C[i]+1);
  48.     for(int i=1;i<=3;i++)
  49.     {
  50.         if(!st[i].x)continue;
  51.         memset(dist,0,sizeof(dist));
  52.         queue<int> Qx,Qy;
  53.         Qx.push(st[i].x);
  54.         Qy.push(st[i].y);
  55.         dist[st[i].x][st[i].y]=1;
  56.         while(!Qx.empty())
  57.         {
  58.             int X=Qx.front();Qx.pop();
  59.             int Y=Qy.front();Qy.pop();
  60.             for(int k=0;k<4;k++)
  61.             {
  62.                 int XX=X+dx[k];
  63.                 int YY=Y+dy[k];
  64.                 if(!dist[XX][YY]&&(C[XX][YY]=='.'||C[XX][YY]==i+'0'||C[XX][YY]=='F'))
  65.                 {
  66.                     dist[XX][YY]=1+dist[X][Y];
  67.                     Qx.push(XX);
  68.                     Qy.push(YY);
  69.                 }
  70.             }
  71.         }
  72.         if(dist[st[4].x][st[4].y]&&rez>dist[st[4].x][st[4].y])
  73.         {
  74.             rez=dist[st[4].x][st[4].y];
  75.             ind=i;
  76.         }
  77.     }
  78.     printf("%d\n%d",ind,rez-1);
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement