Advertisement
Guest User

Untitled

a guest
Dec 14th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.36 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. typedef
  6.     struct
  7.     {
  8.         int x;
  9.         int y;
  10.     }
  11.     point;
  12.  
  13. using namespace std;
  14.  
  15. ifstream cin("INPUT.TXT");
  16. ofstream cout("OUTPUT.TXT");
  17.  
  18. void in(vector < vector <char> >& a, vector < vector <int> >& p, point& st,point& fn)
  19. {
  20.      
  21.     for (int i=1;i<=a.size()-2;i++)
  22.         for (int j=1;j<=a.size()-2;j++)
  23.         {
  24.             cin>>a[i][j];
  25.             if (a[i][j]=='.') p[i][j]=0; else
  26.                 if (a[i][j]=='@')
  27.                 {
  28.                     p[i][j]=1;
  29.                     st.x=i;
  30.                     st.y=j;
  31.                 } else
  32.                     if (a[i][j]=='X')
  33.                     {
  34.                         p[i][j]=0;
  35.                         fn.x=i;
  36.                         fn.y=j;
  37.                     }
  38.         }
  39. }
  40.  
  41. int main()
  42. {
  43.     int n;
  44.     cin>>n;
  45.     vector <vector <char> >a(n+2, vector <char> (n+2, 'O'));
  46.     vector <vector <int> >p(n+2,vector <int>(n+2,-1));
  47.     queue <point> q;
  48.     point st,fn;
  49.     in(a,p,st,fn);
  50.     q.push(st);
  51.     while (!q.empty())
  52.     {
  53.         point t=q.front();
  54.         q.pop();
  55.         point u;
  56.         if (p[t.x-1][t.y]==0)
  57.         {
  58.             p[t.x-1][t.y]=p[t.x][t.y]+1;
  59.             u.x=t.x-1;
  60.             u.y=t.y;
  61.             q.push(u);
  62.         }
  63.  
  64.             if (p[t.x+1][t.y]==0)
  65.         {
  66.             p[t.x+1][t.y]=p[t.x][t.y]+1;
  67.             u.x=t.x+1;
  68.             u.y=t.y;
  69.             q.push(u);
  70.         }
  71.  
  72.  
  73.             if (p[t.x][t.y-1]==0)
  74.         {
  75.             p[t.x][t.y-1]=p[t.x][t.y]+1;
  76.             u.x=t.x;
  77.             u.y=t.y-1;
  78.             q.push(u);
  79.         }
  80.             if (p[t.x][t.y+1]==0)
  81.         {
  82.             p[t.x][t.y+1]=p[t.x][t.y]+1;
  83.             u.x=t.x;
  84.             u.y=t.y+1;
  85.             q.push(u);
  86.         }
  87.  
  88.     }
  89.     if (p[fn.x][fn.y]==0) cout<<"No"; else
  90.     {
  91.         a[fn.x][fn.y]='+';
  92.         while (fn.x!=st.x || fn.y!=st.y)
  93.         {
  94.             if (p[fn.x-1][fn.y]==p[fn.x][fn.y]-1) fn.x--; else
  95.                 if (p[fn.x+1][fn.y]==p[fn.x][fn.y]-1) fn.x++; else
  96.                     if (p[fn.x][fn.y-1]==p[fn.x][fn.y]-1) fn.y--; else
  97.                         if (p[fn.x][fn.y+1]==p[fn.x][fn.y]-1) fn.y++;
  98.             if (!(fn.x==st.x && fn.y==st.y)) a[fn.x][fn.y]='+';
  99.         }
  100.         cout<<"Yes"<<endl;
  101.         for (int i=1;i<=n;i++)
  102.         {
  103.             for (int j=1;j<=n;j++) cout<<a[i][j];
  104.             cout<<endl;
  105.         }
  106.     }
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement