AcWing 756. 蛇形矩阵好理解的模拟法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 756. 蛇形矩阵好理解的模拟法原题链接困难

作者：

萌萌和 , 2020-01-30 14:37:05 , 所有人可见 , 阅读 17800

193

107

题解

利用 left right top bottom 四个变量来表示这个矩形的边界

#include <iostream>

using namespace std;
const int N = 105;

int a[N][N];
int n, m;

int main() {
    cin >> n >> m;

    int left = 0, right = m - 1, top = 0, bottom = n - 1;
    int k = 1;
    while (left <= right && top <= bottom) {
        for (int i = left ; i <= right; i ++) {
            a[top][i] = k ++;
        }
        for (int i = top + 1; i <= bottom; i ++) {
            a[i][right] = k ++;
        }
        for (int i = right - 1; i >= left && top < bottom; i --) {
            a[bottom][i] = k ++;
        }
        for (int i = bottom - 1; i > top && left < right; i --) {
            a[i][left] = k ++;
        }
        left ++, right --, top ++, bottom --;
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

51 评论

Bingxiu 2023-02-17 20:53

利用碰撞探测法，可以写出特别短的代码

下界合金镐 2022-02-15 21:05

代码比我还长hhh（我22行和y总一样）

r.c.l 2022-03-12 09:28

&& top < bottom && left < right这种边界情况怎么想出来的，太厉害了吧

叶藏1 2022-09-22 01:42

同问，为啥呢

月弦音 2023-10-26 20:05 回复了叶藏1 的评论

每一轮循环结束边界点更新后，假如top==bottom，这时在第二轮我们进行向←走时，那么我们就原路返回了（因为这时我们将要走的横行即bottom和我们来的时候走的横行top是同一横行）

lll_181 2023-11-01 16:54

我对着草稿纸花了五六分钟才看明白这两个边界问题，就是为了防止最后两个for循环在左右边界相等或者上下边界相等的时候继续读入导致覆盖前面的

爱德华必上岸 2023-04-22 16:30

通俗易懂牛比1

Hasity 2021-01-11 14:14

牛

GanaWeng 8个月前

两个数据TLE了，求大神指教

#include <iostream>

using namespace std;

int n, m;

int main()
{
    cin >> n >> m;
    int M[n][m];

    bool d[n][m];

    int k = 1; M[0][0] = 1, d[0][0] = true;
    int x[4] = {0, 1, 0, -1}, y[4] = {1, 0, -1, 0};

    int i = 0, j = 0, u = 0; 

    while(k < n * m)
    {
        if(i + x[u] < n && j + y[u] < m && i + x[u] >= 0 && j + y[u] >= 0 && (!d[i + x[u]][j + y[u]]))
        {
            i = i + x[u];
            j = j + y[u];
            ++ k;
            M[i][j] = k;
            d[i][j] = true;   
        }
        else u = (u + 1) % 4;
    }

    for(int i = 0 ; i < n; i ++)
    {
        for(int j = 0 ; j < m; j ++)
        {    
            cout << M[i][j] << ' ';
        }
        cout << endl;
    }

}