1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdint>
#include <algorithm>
using namespace std;

struct Coords {
    int16_t i, j;

    Coords() {}
    Coords(int16_t ii, int16_t jj) : i(ii), j(jj) {}

    void set(int16_t ii, int16_t jj) {
        i = ii; j = jj;
    }
};

const int16_t N = 3000;
const int32_t N2 = N*N;
const int8_t K = 4;
const int8_t K1 = K+1;
const int32_t Mod = 1000000007;
const char Empty = '.';
const char Tile = '#';
const Coords Nbr[] = { Coords(-1, 0), Coords(0, -1), Coords(0, 1), Coords(1, 0)};
const int8_t NbrLen = 4;

int main() {
    char c;
    int16_t i, j, n;
    int32_t ii;
    int16_t k, lvl, nbrCount; // 8 is enough, but things has happened
    int64_t sum = 0;

    int8_t **visited = new int8_t*[N];
    for (i=0; i<N; ++i) { visited[i] = new int8_t[N]; }

    Coords *opt = new Coords[N2];
    int32_t *skip = new int32_t[N2]();

    int32_t optLen = 0;
    int32_t todo[K1] = { 0 };
    int32_t ptr[K1] = {};
        fill_n(ptr, K1, 0);
    int32_t lvlOptCount[K1] = { 0 };

    int32_t curi; // current index
    Coords *cur; // current Coords
    Coords nbr;

    //--------------------------------

    cin >> n >> k;
    lvl = k;

    for (i=0; i<n; ++i) {
        for (j=0; j<n; ++j) {
            cin >> c;
            if (c == Tile) {
                visited[i][j] = 1;
            } else {
                visited[i][j] = 0;
            }
        }
    }

    for (i=0; i<n; ++i) {
        for (j=0; j<n; ++j) {
            if (!visited[i][j]
                && ((i > 0 && visited[i-1][j])
                    || (j > 0 && visited[i][j-1])
                    || (j < n-1 && visited[i][j+1])
                    || (i < n-1 && visited[i+1][j]))) {
                opt[optLen++].set(i, j);
            }
        }
    }
    for (curi=0; curi<optLen; ++curi) {
        cur = &opt[curi];
        visited[cur->i][cur->j] = 1;
    }
    todo[lvl] = optLen;
    ptr[lvl] = optLen-1;
    lvlOptCount[lvl] = optLen;

    //--------------------------------

    while (optLen > 0) {
        if (lvl == 1 || ptr[lvl] == -1) {
            if (lvl == 1) {
                sum = (sum + lvlOptCount[lvl]) % Mod;
            }
            for (ii=0; ii<todo[lvl]; ++ii) {
                cur = &opt[--optLen];
                visited[cur->i][cur->j] = 0;
            }
            todo[lvl] = 0;
            ptr[lvl] = -1;
            ++lvl;
        } else {
            curi = ptr[lvl];
            cur = &opt[curi];
            ptr[lvl] -= skip[curi] + 1;
            --lvlOptCount[lvl];
            nbrCount = 0;
            for (ii=0; ii<NbrLen; ++ii) {
                nbr.set(cur->i + Nbr[ii].i, cur->j + Nbr[ii].j);
                if (nbr.i >= 0 && nbr.i < n && nbr.j >= 0 && nbr.j < n
                    && !visited[nbr.i][nbr.j]) {
                    skip[optLen] = 0;
                    opt[optLen++].set(nbr.i, nbr.j);
                    visited[nbr.i][nbr.j] = 1;
                    ++nbrCount;
                }
            }
            if (nbrCount) {
                skip[optLen - nbrCount] =
                        skip[curi] + (optLen - nbrCount - curi);
                todo[lvl-1] = nbrCount;
                ptr[lvl-1] = optLen-1;
            } else {
                ptr[lvl-1] = curi - skip[curi] - 1;
            }
            lvlOptCount[lvl-1] = lvlOptCount[lvl] + nbrCount;
            --lvl;
        }
    }
    cout << sum;

    return 0;
}