Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <iostream>
- #include <queue>
- using namespace std;
- const double EPS = 1e-5;
- char Gr[101][101];
- bool used[101][101];
- int best=-1, X[2],Y[2];
- int n,m;
- struct ver
- {
- int num;
- int i;
- int j;
- ver(int N,int I,int J)
- {
- num = N;
- i = I;
- j = J;
- }
- };
- void clear()
- {
- for(int i=1;i<=100;++i)
- for(int j=1;j<=100;++j)
- used[i][j] = false;
- }
- void bfs(int i,int j)
- {
- clear();
- queue < ver > q;
- if(Gr[i][j]=='-') return;
- q.push( ver(0,i,j) );
- while(!q.empty())
- {
- ver temp = q.front(); q.pop();
- if(used[temp.i][temp.j]) continue;
- used[temp.i][temp.j] = true;
- if(temp.num>best)
- {
- best = temp.num;
- X[0] = i;
- Y[0] = j;
- X[1] = temp.i;
- Y[1] = temp.j;
- }
- if(temp.i>1 && Gr[temp.i-1][temp.j]=='#' && !used[temp.i-1][temp.j])
- {
- q.push(ver(temp.num+1,temp.i-1,temp.j));
- }
- if(temp.i<n && Gr[temp.i+1][temp.j]=='#'&& !used[temp.i+1][temp.j])
- {
- q.push(ver(temp.num+1,temp.i+1,temp.j));
- }
- if(temp.j>1 && Gr[temp.i][temp.j-1]=='#' && !used[temp.i][temp.j-1])
- {
- q.push(ver(temp.num+1,temp.i,temp.j-1));
- }
- if(temp.j<m && Gr[temp.i][temp.j+1]=='#' && !used[temp.i][temp.j+1])
- {
- q.push(ver(temp.num+1,temp.i,temp.j+1));
- }
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> n >> m;
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=m;++j)
- {
- cin >> Gr[i][j];
- }
- }
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=m;++j)
- {
- bfs(i,j);
- }
- }
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=m;++j)
- {
- if( (i==X[0] && j==Y[0]) || (i==X[1] && j==Y[1])) cout << 'X';
- else cout << Gr[i][j];
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement