算法分析

模拟

• 1、4个while循环，分别对应向右，向下，向左，向上走，走一趟为一个周期
• 2、若在当前方向的下一个位置可以踩，则踩过去

时间复杂度 $O(n^2)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

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

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

    int k = 0;
    int x = 0, y = -1;
    while(k != n * m)
    {
        //向右走
        while(y + 1 < m && a[x][y + 1] == 0)
        {
            y ++;
            a[x][y] = ++ k;
        }
        //向下走
        while(x + 1 < n && a[x + 1][y] == 0)
        {
            x ++;
            a[x][y] = ++ k;
        }
        //向左走
        while(y - 1 >= 0 && a[x][y - 1] == 0)
        {
            y --;
            a[x][y] = ++ k;
        }
        //向上走
        while(x - 1 >= 0 && a[x - 1][y] == 0)
        {
            x --;
            a[x][y] = ++ k;
        }
    }

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

    return 0;
}