[COCI2014-15#6] METEOR

题目描述

给定一个字符矩阵，在保证 # 与 X 不重合的情况下整体向下平移 X ，输出平移距离最长的答案

思路

对于每一列，处理出最下方的 X 与最上方的 # 的距离。这样会得到 S 个距离，哪么最多能平移的距离即为这些距离中的最小值。

直接暴力模拟平移即可。

时间复杂度: $O(R \ \cdot \ S)$

代码

个人码风比较丑，写得又臭又长，见谅。

#include <iostream>
using namespace std;

const int MAXN = 3 * 1000 + 10;
const int inf = 999999999;

int R , S;

char Map[MAXN][MAXN];

char Ans[MAXN][MAXN];

int Dist[MAXN] , Move = inf;

int main() {
    cin >> R >> S;

    for(int i = 1; i <= R; i++) {
        getchar();
        for(int j = 1; j <= S; j++) {
            Dist[j] = inf;
            Map[i][j] = getchar();
            if(Map[i][j] == '#') {
                Ans[i][j] = '#';
            }
            else Ans[i][j] = '.';
        }
    }
    
    for(int i = 1; i <= S; i++) {
        for(int j = 1; j <= R; j++) {
            if(Map[j][i] == 'X') {
                Dist[i] = 0;
                for(int k = j + 1; k <= R; k++) {
                    if(Map[k][i] == 'X') {
                        Dist[i] = 0;
                        continue;
                    }
                    if(Map[k][i] == '#') break;
                    Dist[i]++;
                }
                break;
            }
        }
    }

    for(int i = 1; i <= S; i++) {
        Move = min(Move , Dist[i]);
    }

    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= S; j++) {
            if(Map[i][j] == 'X') {
                Ans[i + Move][j] = 'X';
            }
        }
    }

    // putchar('\n');

    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= S; j++) {
            putchar(Ans[i][j]);
        }
        putchar('\n');
    }

    return 0;
}