v 0. Pasted by slipstak2 as cpp at 2010-11-23 23:02:55 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 6.
  2. // 6E. Lines [lines]
  3. // ibelyaev: 23Nov2010
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <queue>
  9. #include <cstring>
  10.  
  11. using namespace std;
  12.  
  13. struct point
  14. {
  15.     int x,y;
  16.     point(){}
  17.     point(int X, int Y)
  18.     {
  19.         x = X;
  20.         y = Y;
  21.     }
  22. };
  23. bool operator == (const point &a, const point &b)
  24. {
  25.     return a.x == b.x && a.y == b.y;
  26. }
  27. const int max_size = 45;
  28. int n;
  29. char mas[max_size][max_size];
  30. int  f[max_size][max_size];
  31. point begin,end;
  32. void input()
  33. {
  34.     scanf("%d\n", &n);
  35.    
  36.     char c;
  37.     for (int i=0;i<n;i++)
  38.     {
  39.         for (int j=0;j<n;j++)
  40.         {
  41.             scanf("%c",&c);
  42.             mas[i][j] = c;
  43.             if (c == '@')
  44.                 begin = point(i,j);
  45.             if (c == 'X')
  46.                 end = point(i,j);
  47.         }
  48.         scanf("%c",&c); // считываем '\n'
  49.     }
  50. }
  51. int moveX[4] = {0,1,0,-1};
  52. int moveY[4] = {1,0,-1,0};
  53. bool correct(int x, int y)
  54. {
  55.     if (x<0 || y<0)
  56.         return false;
  57.     if (x==n || y==n)
  58.         return false;
  59.     return true;
  60. }
  61. void findWay()
  62. {
  63.     memset(f,0,sizeof(f));
  64.     f[begin.x][begin.y] = 1;
  65.     queue<point> q;
  66.     q.push(begin);
  67.     while (!q.empty())
  68.     {
  69.         point cur = q.front(); q.pop();
  70.         for (int i=0;i<4;i++)
  71.         {
  72.             int x = cur.x + moveX[i];
  73.             int y = cur.y + moveY[i];
  74.             if (correct(x,y) && f[x][y]==0 && mas[x][y] != 'O')
  75.             {
  76.                 point next(x,y);
  77.                 f[x][y] = f[cur.x][cur.y] + 1;
  78.                 if (next == end)
  79.                     return;
  80.                 q.push(next);
  81.             }
  82.         }
  83.     }
  84. }
  85. void findAnswer()
  86. {
  87.     point cur = end;
  88.     int value = f[end.x][end.y]-1;
  89.     mas[end.x][end.y] = '+';
  90.     while (!(cur==begin))
  91.     {
  92.         for (int i=0;i<4;i++)
  93.         {
  94.             int x = cur.x + moveX[i];
  95.             int y = cur.y + moveY[i];
  96.             if (correct(x,y) && f[x][y] == value)
  97.             {
  98.                 value--;
  99.                 if (value != 0)
  100.                     mas[x][y] = '+';
  101.                 cur = point(x,y);
  102.                 break;
  103.             }
  104.         }
  105.     }
  106.  
  107. }
  108. void output()
  109. {
  110.     for (int i=0;i<n;i++)
  111.     {
  112.         for (int j=0;j<n;j++)
  113.             printf("%c",mas[i][j]);
  114.         printf("\n");
  115.     }
  116. }
  117. void solve()
  118. {
  119.     findWay();
  120.     if (!f[end.x][end.y])
  121.         printf("N");
  122.     else
  123.     {
  124.         printf("Y\n");
  125.         findAnswer();
  126.         output();
  127.     }
  128. }
  129.  
  130. int main()
  131. {
  132.     freopen("input.txt","r",stdin);
  133.     freopen("output.txt","w",stdout);
  134.    
  135.     input();
  136.     solve();
  137.     return 0;
  138. }


Editing is locked.