fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long int 
  5. #define str string
  6. #define pb push_back
  7. #define vc vector
  8. #define ci cin
  9. #define co cout
  10. ll vis[1010][1010],n,m,dp[1010][1010];
  11. string s[1010];
  12. // remove fropen in online judge
  13. void dfs(ll i,ll j,ll len)
  14. {     
  15.  
  16.      if(i-1>=0&&s[i-1][j]!='#'&&dp[i-1][j]>len)
  17.      {
  18.         dp[i-1][j]=min(dp[i-1][j],len);
  19.           dfs(i-1,j,len+1);
  20.      }
  21.      if(j-1>=0&&s[i][j-1]!='#'&&dp[i][j-1]>len)
  22.      {
  23.         dp[i][j-1]=min(dp[i][j-1],len);
  24.         dfs(i,j-1,len+1);
  25.      }
  26.       if(i+1<n&&s[i+1][j]!='#'&&dp[i+1][j]>len)
  27.       {
  28.         dp[i+1][j]=min(dp[i+1][j],len);
  29.         dfs(i+1,j,len+1);
  30.       }
  31.        if(j+1<m&&s[i][j+1]!='#'&&dp[i][j+1]>len)
  32.       {
  33.         dp[i][j+1]=len;
  34.         dfs(i,j+1,len+1);
  35.       }
  36.       //  return dp[i][j];
  37.  
  38. }
  39. int main()
  40. { 
  41.      #ifndef ONLINE_JUDGE 
  42.      freopen("input.txt","r",stdin);
  43.      freopen("output.txt","w",stdout);
  44.      freopen("error.txt","w",stderr);
  45.     #endif 
  46.  
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     cin>>n>>m;
  50.  
  51.  
  52.     for(int i=0;i<n;i++)
  53.         cin>>s[i];
  54.     ll ct=0;
  55.     for(int i=0;i<n;i++)
  56.     {
  57.         for(int j=0;j<m;j++)
  58.         {dp[i][j]=INT_MAX;
  59.             vis[i][j]=false;
  60.         }
  61.     }
  62.     ll bi,bj;
  63.     for(int i=0;i<n;i++)
  64.     {
  65.         for(int j=0;j<m;j++)
  66.         {
  67.             if(s[i][j]=='A')
  68.             {   dp[i][j]=0;
  69.                dfs(i,j,1);
  70.             }  
  71.             if(s[i][j]=='B')
  72.             {
  73.                 bi=i;
  74.                 bj=j;            }
  75.  
  76.         }
  77.     }
  78.     for(int i=0;i<n;i++)
  79.     {
  80.      for(int j=0;j<m;j++)
  81.      cout<<dp[i][j]<<" ";
  82.      cout<<"\n";
  83.     }
  84.     if(dp[bi][bj]==INT_MAX)
  85.         cout<<"NO";
  86.     else
  87.     {
  88.         cout<<"YES\n"<<dp[bi][bj]<<"\n";
  89.         ll i=bi,j=bj;
  90.         str st;
  91.         while(s[i][j]!='A')
  92.         {
  93.             if(i-1>=0&&dp[i-1][j]==dp[i][j]-1)
  94.             {
  95.                 st+='D';
  96.                 i--;
  97.             }
  98.             else if(j-1>=0&&dp[i][j-1]==dp[i][j]-1)
  99.             {
  100.                 st+='R';
  101.                 j--;
  102.             }
  103.             else if(i+1<n&&dp[i+1][j]==dp[i][j]-1)
  104.             {
  105.                 st+='U';
  106.                 i++;
  107.             }
  108.             else if(j+1<m&&dp[i][j+1]==dp[i][j]-1)
  109.             {
  110.                 st+='L';
  111.                 j++;
  112.             }
  113.         }
  114.         for(int i=st.size()-1;i>=0;i--)
  115.         cout<<st[i];
  116.     }
  117.  
  118. }
  119.  
Runtime error #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SfkTKg
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!