Advertisement
Guest User

Untitled

a guest
Oct 7th, 2012
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1.  
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. const double EPS = 1e-5;
  9.  
  10. char Gr[101][101];
  11. bool used[101][101];
  12.  
  13. int best=-1, X[2],Y[2];
  14. int n,m;
  15. struct ver
  16. {
  17.     int num;
  18.     int i;
  19.     int j;
  20.     ver(int N,int I,int J)
  21.     {
  22.         num = N;
  23.         i = I;
  24.         j = J;
  25.     }
  26. };
  27. void clear()
  28. {
  29.     for(int i=1;i<=100;++i)
  30.         for(int j=1;j<=100;++j)
  31.             used[i][j] = false;
  32. }
  33.  
  34. void bfs(int i,int j)
  35. {
  36.     clear();
  37.     queue < ver > q;
  38.     if(Gr[i][j]=='-') return;
  39.     q.push( ver(0,i,j) );
  40.     while(!q.empty())
  41.     {
  42.         ver temp = q.front(); q.pop();
  43.         if(used[temp.i][temp.j]) continue;
  44.         used[temp.i][temp.j] = true;
  45.         if(temp.num>best)
  46.         {
  47.             best = temp.num;
  48.             X[0] = i;
  49.             Y[0] = j;
  50.             X[1] = temp.i;
  51.             Y[1] = temp.j;
  52.         }
  53.         if(temp.i>1 && Gr[temp.i-1][temp.j]=='#' && !used[temp.i-1][temp.j])
  54.         {
  55.             q.push(ver(temp.num+1,temp.i-1,temp.j));
  56.         }
  57.         if(temp.i<n && Gr[temp.i+1][temp.j]=='#'&& !used[temp.i+1][temp.j])
  58.         {
  59.             q.push(ver(temp.num+1,temp.i+1,temp.j));
  60.         }
  61.         if(temp.j>1 && Gr[temp.i][temp.j-1]=='#' && !used[temp.i][temp.j-1])
  62.         {
  63.             q.push(ver(temp.num+1,temp.i,temp.j-1));
  64.         }
  65.         if(temp.j<m && Gr[temp.i][temp.j+1]=='#' && !used[temp.i][temp.j+1])
  66.         {
  67.             q.push(ver(temp.num+1,temp.i,temp.j+1));
  68.         }
  69.     }
  70.  
  71.  
  72. }
  73.  
  74.  
  75.  
  76. int main() {
  77.    
  78.    
  79.     freopen("input.txt", "r", stdin);
  80.     freopen("output.txt", "w", stdout);
  81.    
  82.    
  83.     cin >> n >> m;
  84.     for(int i=1;i<=n;++i)
  85.     {  
  86.         for(int j=1;j<=m;++j)
  87.         {  
  88.             cin >> Gr[i][j];
  89.         }
  90.     }
  91.    
  92.     for(int i=1;i<=n;++i)
  93.     {  
  94.         for(int j=1;j<=m;++j)
  95.         {  
  96.             bfs(i,j);
  97.         }
  98.     }
  99.     for(int i=1;i<=n;++i)
  100.     {
  101.         for(int j=1;j<=m;++j)
  102.         {
  103.             if( (i==X[0] && j==Y[0]) || (i==X[1] && j==Y[1])) cout << 'X';
  104.             else cout << Gr[i][j];
  105.  
  106.         }
  107.         cout << endl;
  108.     }
  109.  
  110.  
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement