Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <iostream>
- # include <cstdio>
- # include <ctime>
- # include <cstdlib>
- # include <cmath>
- # define for(xxx, yyy, zzz) for(int xxx = yyy; xxx <= zzz; ++xxx)
- using namespace std;
- const int MAXN = int(1e2) + 4;
- const int INF = int(1e4);
- const int MN = int(1e4) + 4;
- char s[MAXN][MAXN];
- short dx[] = {1, -1, 0, 0};
- short dy[] = {0, 0, 1, -1};
- short qx[MN], qy[MN], qh, qt;
- short dp[MAXN][MAXN];
- short c[MAXN][MAXN];
- int n, m, col = 1;
- short aa, bb, cc, dd, Maxans;
- int main () {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- scanf("%d %d\n", &n, &m);
- for (i, 1, n)
- for (j, 1, m) {
- scanf("%c", &s[i][j]);
- if(j == m) scanf("\n");
- dp[i][j] = INF;
- c[i][j] = 1;
- }
- for (i, 1, n) {
- for (j, 1, m) {
- if(s[i][j] == '#') {
- qt = qh = 0;
- qh ++;
- qx[qh] = i; qy[qh] = j;
- dp[i][j] = 0;
- }
- else continue;
- while (qt < qh) {
- qt ++;
- short xx = qx[qt], yy = qy[qt];
- if(dp[xx][yy] > Maxans) {
- if(aa != i)aa = i;
- if(bb != j)bb = j;
- cc = xx;
- dd = yy;
- Maxans = dp[xx][yy];
- }
- for (it, 0, 3) {
- if(xx + dx[it] <= n && xx + dx[it] >= 1 && yy + dy[it] <= m && yy + dy[it] >= 1)
- if(s[xx + dx[it]][yy + dy[it]] == '#' && dp[xx][yy] + 1 < dp[xx + dx[it]][yy + dy[it]])
- if(c[xx + dx[it]][yy + dy[it]] == col){
- qh ++;
- qx[qh] = xx + dx[it];
- qy[qh] = yy + dy[it];
- dp[xx + dx[it]][yy + dy[it]] = dp[xx][yy] + 1;
- }
- }
- c[xx][yy] = col + 1;
- dp[xx][yy] = INF;
- }
- col ++;
- }
- }
- s[aa][bb] = 'X';
- s[cc][dd] = 'X';
- for (i, 1, n) {
- for (j, 1, m) {
- putchar(s[i][j]);
- }
- puts("");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment