算法标签：

递推 动态规划

题解

对于算法上面，只能说，用不同的数据结构去存放你已经完成过的查询，以减少你的查询次数，有些类似于动态规划的一部分。（虽然这道题最终是WR但是，我觉得题目的要求已经达到了，能过所有测试数据，可能细节还需考究） 一种是对于大数的处理，合理运用数据结构去存放很重要，然后一种是对于一个平面内很多点之间找到两个最短相距的点，首先是把平面分成两半，然后对于每一半去找最短的距离的点，然后对于两半的最短点距求min，然后对于这个最小值还要进行处理，把最前面的分割线两边加上min在，2min距离内的点集求最小距离的点，看有无比min小的，如果有，那才是最优解，这里还可以运用分治的思想，继续不断的划分直到问题能够简单的解决为止，最后再进行整合。

#include <iostream>
#include <cstring>
using namespace std;

char a[10][81];
int n, r, c; // n--num of symbols, r/c--num of rows/cols in each grid
int upper_bound;

bool search(int x) {
    int begin = x * (c + 1);
    int end = begin + c - 1; // inclusive
    for (int i = 0; i < r; i++) {
        for (int j = begin; j <= end; j++) {
            if (a[i][j] == 'o') {
                int k = j; // forward,backward
                while (k >= c + 1) {
                    k -= (c + 1);
                }
                for (; k <= upper_bound; k += c + 1) {
                    if (a[i][k] != '.' && k != j) {
                        break;
                    }
                }
                if (k <= upper_bound) { // find another
                    continue;
                }
                else {
                    a[i][j] = '#';
                    return true;
                }
            }
        }
    }
    // check 2#...
    //
    for (int i = 0; i < r; i++) {
        for (int j = begin; j <= end; j++) {
            if (a[i][j] != 'o') {
                continue;
            }
            for (int s = i; s < r; s++) {
                for (int t = (s == i? j + 1 : begin); t <= end; t++) {
                    if (a[s][t] != 'o') {
                        continue;
                    }
                    int k1 = j, k2 = t; // forward,backward
                    while (k1 >= c + 1) {
                        k1 -= (c + 1);
                        k2 -= (c + 1);
                    }
                    for (; k1 <= upper_bound; k1 += c + 1, k2 += c + 1) {
                        if (a[i][k1] != '.' && a[s][k2] != '.' && k1 != j) {
                            break;
                        }
                    }
                    if (k1 <= upper_bound) { // find another
                        continue;
                    }
                    else {
                        a[i][j] = '#';
                        a[s][t] = '#';
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    int i;
    int cnt = 1;
    while (true) {
        cin >> n >> r >> c;
        if (cin.eof() || n == 0) {
            break;
        }
        cout << "Test " << cnt++ << endl;
        upper_bound = (c + 1) * (n - 1) + c - 1; // last element
        cin.ignore(); // 忽略输入流中的换行符
        for (i = 0; i < r; i++) {
            cin.getline(a[i], 81);
        }
        for (i = 0; i < n; i++) {
            if (!search(i)) { // check whether symbol i has unique #
                cout << "impossible" << endl;
                break;
            }
        }
        if (i == n) {
            for (i = 0; i < r; i++) {
                cout << a[i] << endl;
            }
        }
    }
    return 0;
}