题解 P4614 【[COCI2017-2018#5] Spirale】

· · 题解

好久没写博客了啊……来水一发……

题意描述

为什么这样一道英文题不支持提供翻译……

给你一个n\times m的矩阵和矩阵内的q个螺旋线，在矩阵上填入螺旋线遍历到该点的编号，求最终的矩阵。

螺旋线的由初始点和方向（顺时针或逆时针）定义，且矩阵右上角为(1,1)。
顺时针线是由初始点向上一个单位，向右一个单位，向下两个单位，向左两个单位，再向上三个单位……以此类推。 同理，逆时针线是由初始点向上一个单位，向左一个单位，向下两个单位，向右两个单位，再向上三个单位……以此类推。

当两条线覆盖到同一个格子时，取较小的编号。 如果螺旋线到了矩阵外，不需要处理，但是编号要保持增加，最后只输出矩阵内的元素。

样例解释

好像只有样例三看不懂

样例三：

3 3 2  
1 1 0  
1 2 0

输出：

1  1  4
6  5  5
19 18 17

先看第一个螺旋线，构造出来应该是这样的：

   .  .  .  .
   .  .  .  .
   .  .  .  .
...10 11 12 13...
...9  2  3  14...
...8  1  4  15...
...7  6  5  16...
...20 19 18 17...
   .  .  .  .
   .  .  .  .
   .  .  .  .

这是一个5\times 4的矩阵，但是我们只取右下角的3\times 3。 再只看第二个螺旋线，可得：

   .  .  .  .
   .  .  .  .
   .  .  .  .
...10 11 12 13...
...9  2  3  14...
...8  1  4  15...
...7  6  5  16...
...20 19 18 17...
   .  .  .  .
   .  .  .  .
   .  .  .  .

这还是一个5\times 4的矩阵，但是我们只取左下角的3\times 3。 于是合并两个3\times3的矩阵，得到答案：

1  1  4
6  5  5
19 18 17

说了这么多，大模拟
强势模拟绕的过程，不是就直接走，判断出了几条界，出了四条街就停

时间复杂度：最多不会长宽多走一倍，所以是O(4nmq)

Code

int n, m, k;
bool out[4];
int mp[51][51];
inline void check(int x, int y) {
    if(x < 1) out[0] = 0;
    if(y < 1) out[1] = 0;
    if(x > n) out[2] = 0;
    if(y > m) out[3] = 0;
}
inline void draw(int&x, int&y, int way, int&num, char ty) {
    for(int i = 1; i <= way; i++) {
        if(ty == 'u') x--;
        if(ty == 'd') x++;
        if(ty == 'l') y--;
        if(ty == 'r') y++;
        check(x, y);
        num++;
        if(x >= 1 && y >= 1 && x <= n && y <= m)
            mp[x][y] = Min(mp[x][y], num);
    }
}
int main() {
    memset(mp, 0x3f, sizeof mp);
    read(n), read(m), read(k);
    for(int i = 1; i <= k; i++) {
        int x, y, ty; read(x), read(y), read(ty);
        int dis = 0, num = 1;
        out[0] = out[1] = out[2] = out[3] = 1;
        mp[x][y] = num;
        while(out[0] || out[1] || out[2] || out[3]) {
            if(ty == 0) {
                draw(x, y, dis / 2 + 1, num, 'u'); dis++;
                draw(x, y, dis / 2 + 1, num, 'r'); dis++;
                draw(x, y, dis / 2 + 1, num, 'd'); dis++;
                draw(x, y, dis / 2 + 1, num, 'l'); dis++;
            }
            else {
                draw(x, y, dis / 2 + 1, num, 'u'); dis++;
                draw(x, y, dis / 2 + 1, num, 'l'); dis++;
                draw(x, y, dis / 2 + 1, num, 'd'); dis++;
                draw(x, y, dis / 2 + 1, num, 'r'); dis++;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < m; j++)
            printf("%d ", mp[i][j]);
        printf("%d\n", mp[i][m]);
    }
}

至于前方的模板——https://www.luogu.org/paste/7ihr6633