38.填充矩阵I

// 与java题解思路一致
// 直接模拟
#include <bits/stdc++.h>
using namespace std;

int n, m;

void solve() {
    vector<vector<int>> res(n,vector<int>(m,0));
    int xHead = 0; // x的最小值
    int yHead = 0; // y的最小值
    int xEnd = n - 1; // x的最大值
    int yEnd = m - 1; // y的最大值
    int x = 0;
    int y = 0;
    int cur = n * m; // 当前应赋的值
    while(cur > 0)
    {
        // 从左到右
        for(; y <= yEnd; ++y)
        {
            // 以下的(cur > 0)都是为了防止把负数赋值上去
            if(cur > 0) 
            res[x][y] = cur--;
        }
        // 以下改变x, y的操作都是为了把越界的或者跑到已经赋值的位置的x, y拉回来
        --y;
        ++x;
        // 从上到下
        for(; x <= xEnd; ++x)
        {
            if(cur > 0)
            res[x][y] = cur--;
        }
        --x;
        --y;
        // 从右到左
        for(; y >= yHead; --y)
        {
            if(cur > 0)
            res[x][y] = cur--;
        }
        ++y;
        --x;
        // 从下到上, 但是不能覆盖已经赋值的部分
        // 所以到xhead为止
        for(; x > xHead; --x)
        {
            if(cur > 0)
            res[x][y]=cur--;
        }
        ++x;
        ++y;
        // 跑完一圈,范围缩紧
        xHead++;
        yHead++;
        yEnd--;
        xEnd--;
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    while(cin >> n >> m) {
        solve();
    }
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int n, m;

/**
 * 模拟整个向内环绕的填入过程
 * 参考资料：https://leetcode.cn/problems/spiral-matrix-ii/solutions/12594/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x/
 * 只是多了个过程中的num判断
 */
void solve()
{
    vector<vector<int>> arr(n, vector<int>(m));
    int num = n * m;
    int left = 0, right = m - 1;
    int top = 0, bottom = n - 1;
    while (num)
    {
        for (int j = left; j <= right && num; j++) // left -> right
            arr[top][j] = num--;
        top++;
        for (int i = top; i <= bottom && num; i++) // top -> bottom
            arr[i][right] = num--;
        right--;
        for (int j = right; j >= left && num; j--) // right -> left
            arr[bottom][j] = num--;
        bottom--;
        for (int i = bottom; i >= top && num; i--) // bottom -> top
            arr[i][left] = num--;
        left++;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    while (cin >> n >> m)
    {
        solve();
    }
    return 0;
}

/**
 * 思路：从内到外模拟过于麻烦，观察到可以从左上角到右下角进行逆向打印。
*/

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] array = generate2dArray2(n, m);
        print2dArray(array, n, m);
    }
    public static int[][] generate2dArray2(int n, int m) {
        int stop = 0;  // 结束条件
        int count = n * m;  // 用于填充二维数组的元素
        int startX = 0;
        int startY = 0;  
        int endX = n;
        int endY = m;
        int[][] twoDArray = new int[n][m];
        while (count > stop) {
            int i = startX;
            int j = startY;
            while (count > stop && j < endY) {  // 从左上到右上
                twoDArray[i][j++] = count--;
            }
            // 每 行/列 循环结束后，调整下一 行/列 开始遍历的位置。
            i++;
            j--;
            while (count > stop && i < endX) {  // 从右上到右下
                twoDArray[i++][j] = count--;
            }
            i--;
            j--;
            while (count > stop && j >= startY) { // 从右下到左下
                twoDArray[i][j--] = count--;
            }
            i--;
            j++;
            // i > startX 的原因是不能覆盖掉本次循环第一个填充的元素
            while (count > stop && i > startX) {  // 从左下到左上
                twoDArray[i--][j] = count--;
            }
            // 调整下一圈开始循环的位置
            startX++;
            startY++;
            endX--;
            endY--;
        }
        return twoDArray;
    }
    public static void print2dArray(int[][] twoDArray, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m - 1; j++) {
                System.out.printf("%d ", twoDArray[i][j]);
            }
            System.out.printf("%d\n", twoDArray[i][m - 1]);
        }
    }
}

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        helper(n, m);
        sc.close();
    }

    /**
     * 初始化一个 n×n 大小的矩阵 mat，然后模拟整个向内环绕的填入过程：
     * 
     * 定义当前左右上下边界 l,r,t,b，初始值 num = n * m，迭代终止值 tar = 1；
     * 当 num >= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
     * 执行 num -= 1：得到下一个需要填入的数字；
     * 更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
     * 使用num >= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
     * 最终返回 mat 即可。
     * 
     * 模拟整个向内环绕的填入过程
     * 参考资料：https://leetcode.cn/problems/spiral-matrix-ii/solutions/12594/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x/
     * 只是多了个过程中的num判断
     * 
     */
    static void helper(int n, int m) {
        int[][] arr = new int[n][m];
        int num = n * m;
        int left = 0, right = m - 1;
        int top = 0, bottom = n - 1;
        while (num > 0) {
            for (int j = left; j <= right && num > 0; j++) // left -> right
                arr[top][j] = num--;
            top++;
            for (int i = top; i <= bottom && num > 0; i++) // top -> bottom
                arr[i][right] = num--;
            right--;
            for (int j = right; j >= left && num > 0; j--) // right -> left
                arr[bottom][j] = num--;
            bottom--;
            for (int i = bottom; i >= top && num > 0; i--) // bottom -> top
                arr[i][left] = num--;
            left++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.printf("%d ", arr[i][j]);
            }
            System.out.println();
        }
    }

}

# 思路：这个很明显就是考察代码随想录中螺旋数组那道题，但是做过很久了，已经忘记当时怎么设置的边界条件了，于是使用了下面一种类似于手动dfs的策略，先向右，再向下，再向左， 再向上的策略
def get_new(res, m, n):
    current = m*n
    x = 0
    y = 0
    count = 0
    while current > 0:
        while y<n and res[x][y] == 0 and current > 0:
            res[x][y] = current
            current -= 1
            y += 1
        y -= 1
        x += 1
        while x<m and res[x][y] == 0 and current > 0:
            res[x][y] = current
            current -= 1
            x += 1
        x -= 1
        y -= 1
        while y>-1 and res[x][y] == 0 and current > 0:
            res[x][y] = current
            current -= 1
            y -= 1
        y += 1
        x -= 1
        while x>-1 and res[x][y] == 0 and current > 0:
            res[x][y] = current
            current -= 1
            x -= 1
        x += 1
        y += 1

m, n = map(int, input().split(" "))
if m == 1 and n == 1:
     print(1)
else:
    res = [[0 for _ in range(n)] for _ in range(m)]
    get_new(res, m, n)
    for i in res:
        tmp = ""
        for k in range(len(i)):
            if k!=len(i)-1:
                tmp += str(i[k]) + " "
            else:
                 tmp += str(i[k])
        print(tmp)

def spiralOrder(n, m):
    """
     模拟整个向内环绕的填入过程
     参考资料：https://leetcode.cn/problems/spiral-matrix-ii/solutions/12594/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x/
     只是多了个过程中的num判断
    """
    matrix = [[0] * m for _ in range(n)]
    num = n * m
    left, right = 0, m - 1
    top, bottom = 0, n - 1

    while num > 0:
        for j in range(left, right + 1):
            if not num:
                break
            matrix[top][j] = num
            num -= 1
        top += 1
        for i in range(top, bottom + 1):
            if not num:
                break
            matrix[i][right] = num
            num -= 1
        right -= 1
        for j in range(right, left - 1, -1):
            if not num:
                break
            matrix[bottom][j] = num
            num -= 1
        bottom -= 1
        for i in range(bottom, top - 1, -1):
            if not num:
                break
            matrix[i][left] = num
            num -= 1
        left += 1

    return matrix


n, m = map(int, input().split())
matrix = spiralOrder(n, m)
for i in range(n):
    for j in range(m):
        print(matrix[i][j], end=" ")
    print()

#include<stdio.h>
#include<stdlib.h>

int n, m;

void solve() {
    int res[100][100];
    int xHead = 0; // x的最小值
    int yHead = 0; // y的最小值
    int xEnd = n - 1; // x的最大值
    int yEnd = m - 1; // y的最大值
    int x = 0;
    int y = 0;
    int cur = n * m; // 当前应赋的值
    while(cur > 0)
    {
        // 从左到右
        for(; y <= yEnd; ++y)
        {
            // 以下的(cur > 0)都是为了防止把负数赋值上去
            if(cur > 0) 
            res[x][y] = cur--;
        }
        // 以下改变x, y的操作都是为了把越界的或者跑到已经赋值的位置的x, y拉回来
        --y;
        ++x;
        // 从上到下
        for(; x <= xEnd; ++x)
        {
            if(cur > 0)
            res[x][y] = cur--;
        }
        --x;
        --y;
        // 从右到左
        for(; y >= yHead; --y)
        {
            if(cur > 0)
            res[x][y] = cur--;
        }
        ++y;
        --x;
        // 从下到上, 但是不能覆盖已经赋值的部分
        // 所以到xhead为止
        for(; x > xHead; --x)
        {
            if(cur > 0)
            res[x][y]=cur--;
        }
        ++x;
        ++y;
        // 跑完一圈,范围缩紧
        xHead++;
        yHead++;
        yEnd--;
        xEnd--;
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    while(scanf("%d %d", &n, &m) != EOF) {
        solve();
    }
    return 0;
}