首页 > 试题广场 >

转圈打印矩阵

[编程题]转圈打印矩阵
  • 热度指数:2031 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整型矩阵matrix,请按照顺时针转圈的方式打印它。

输入描述:
输入包含多行,第一行两个整数n和m,代表矩阵的行数和列数,接下来n行,每行m个整数,代表矩阵matrix


输出描述:
输出包含一行,n*m个整数,代表顺时针转圈输出的矩阵matrix。
示例1

输入

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

备注:
额外空间复杂度O(1)
#include<iostream>
#include<vector>

using namespace std;

void printArray(vector<vector<int>>& arr, int row1, int col1, int row2, int col2)
{
    if (row1 == row2)
        while (col1 <= col2) cout << arr[row1][col1++] << " ";
    else if (col1 == col2)
        while (row1 <= row2) cout << arr[row1++][col1] << " ";
    else
    {
        for (int j=col1; j<col2; j++) cout << arr[row1][j] << " ";
        for (int i=row1; i<row2; i++) cout << arr[i][col2] << " ";
        for (int j=col2; j>col1; j--) cout << arr[row2][j] << " ";
        for (int i=row2; i>row1; i--) cout << arr[i][col1] << " ";
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m,0));
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cin >> arr[i][j];
    int row1 = 0, col1 = 0;
    int row2 = n-1, col2 = m-1;
    while (row1 <= row2 && col1 <= col2)
        printArray(arr, row1++, col1++, row2--, col2--);
    return 0;
}

发表于 2019-10-12 18:26:35 回复(0)
按照左上角和右下角的位置唯一确定一个子矩阵,然后每次打印该子矩阵的外圈。
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> read_matrix() {
    int m, n;
    cin >> m >> n;
    
    auto matrix = vector<vector<int>>(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    return matrix;
}

void print_edge(const vector<vector<int>>& matrix, int leftup_row, int leftup_col, int rightdown_row, int rightdown_col);
void spiral_print_matrix(const vector<vector<int>>& matrix) {
    if (matrix.empty()) return;
    int m = matrix.size();
    int n = matrix[0].size();
    
    int leftup_row = 0, leftup_col = 0;
    int rightdown_row = m - 1, rightdown_col = n - 1;
    while (leftup_row <= rightdown_row && leftup_col <= rightdown_col) {
        print_edge(matrix, leftup_row++, leftup_col++, rightdown_row--, rightdown_col--);
    }
}

void print_edge(const vector<vector<int>>& matrix, int leftup_row, int leftup_col, int rightdown_row, int rightdown_col) { 
    //只有一行
    if (leftup_row == rightdown_row) {
        for (int j = leftup_col; j <= rightdown_col; j++) {
            cout << matrix[leftup_row][j] << " ";
        }
    }
    //只有一列
    else if (leftup_col == rightdown_col) {
        for (int i = leftup_row; i <= rightdown_row; i++) {
            cout << matrix[i][leftup_col] << " ";
        }
    } else {
        int i = leftup_row, j = leftup_col;
        
        while (j < rightdown_col) {
            cout << matrix[leftup_row][j] << " ";
            j++;
        }
        
        while (i < rightdown_row) {
            cout << matrix[i][rightdown_col] << " ";
            i++;
        }
        
        while (j > leftup_col) {
            cout << matrix[rightdown_row][j] << " ";
            j--;
        }
        
        while (i > leftup_row) {
            cout << matrix[i][leftup_col] << " ";
            i--;
        }
    }
}

int main() {
    spiral_print_matrix(read_matrix());
}


发表于 2022-07-07 14:55:49 回复(0)
这个题不要一开始就想着转圈,宏观点来分析。其实每一轮我们就是在顺时针打印边框,比如示例:(1) 从左上角开始,先顺时针打印最外层的边框:1 2 3 4 8 12 16 15 14 13 9 5;(2) 又到了左上角,再顺时针打印第二层的边框:5 6 11 10。而用左上角和右下角的索引就能够唯一定位出一个矩形框,所以我们可以每次打印一个框,最外层框打印完了左上角向右下角移动,右下角向左上角移动打印次外层框,直到两个固定边框的点错过。
#include<iostream>
#include<vector>

using namespace std;

// 打印左上角和右下角定位出来的框
void printEdge(vector<vector<int>>& arr, int leftTopX, int leftTopY, int rightBottomX, int rightBottomY) {
    if(leftTopX == rightBottomX){      // 此时只有一行
        for(int i = leftTopY; i <= rightBottomY; i++) cout << arr[leftTopX][i] << " ";
    }else if(leftTopY == rightBottomY){      // 此时只有一列
        for(int i = leftTopX; i <= rightBottomX; i++) cout << arr[i][leftTopY] << " ";
    }else{     // 常规情况,转圈打印
        for(int i = leftTopY; i < rightBottomY; i++) cout << arr[leftTopX][i] << " ";
        for(int i = leftTopX; i < rightBottomX; i++) cout << arr[i][rightBottomY] << " ";
        for(int i = rightBottomY; i > leftTopY; i--) cout << arr[rightBottomX][i] << " ";
        for(int i = rightBottomX; i > leftTopX; i--) cout << arr[i][leftTopX] << " ";
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> arr[i][j];
    int leftTopX = 0, leftTopY = 0;        // 左上角
    int rightBottomX = n - 1, rightBottomY = m - 1;     // 右下角
    while(leftTopX <= rightBottomX && leftTopY <= rightBottomY)
        printEdge(arr, leftTopX++, leftTopY++, rightBottomX--, rightBottomY--);
    return 0;
}
根据以上的思想,可以知道在进行每条边的打印时,只要限制住端点就行,进一步得到如下的虚拟边界法。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int m = Integer.parseInt(params[0]), n = Integer.parseInt(params[1]);
        String[][] matrix = new String[m][n];
        for(int i = 0; i < m; i++){
            String[] row = br.readLine().trim().split(" ");
            for(int j = 0; j < n; j++)
                matrix[i][j] = row[j];
        }
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        int start = 0;
        while(start < m*n){
            for(int i = left; i <= right; i++){
                start ++;
                System.out.print(matrix[top][i] + " ");
            }
            top ++;
            if(top > bottom) continue;
            for(int i = top; i <= bottom; i++) {
                start ++;
                System.out.print(matrix[i][right] + " ");
            }
            right --;
            if(right < left) continue;
            for(int i = right; i >= left; i--){
                start ++;
                System.out.print(matrix[bottom][i] + " ");
            }
            bottom --;
            if(top > bottom) continue;
            for(int i = bottom; i >= top; i--) {
                start ++;
                System.out.print(matrix[i][left] + " ");
            }
            left ++;
            if(right < left) continue;
        }
    }
}

编辑于 2021-11-23 09:43:04 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k=0;
    scanf("%d%d", &n, &m);
    int a[n][m], l=0, r=m-1, u=0, b=n-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d", &a[i][j]);
    while(k<n*m){
        for(int j=l;j<=r && k<n*m;j++){
            printf("%d ", a[u][j]);
            k++;
        }
        u++;
        for(int i=u;i<=b && k<n*m;i++){
            printf("%d ", a[i][r]);
            k++;
        }
        r--;
        for(int j=r;j>=l && k<n*m;j--){
            printf("%d ", a[b][j]);
            k++;
        }
        b--;
        for(int i=b;i>=u && k<n*m;i--){
            printf("%d ", a[i][l]);
            k++;
        }
        l++;
    }
    return 0;
}

发表于 2020-06-05 00:54:38 回复(0)
import java.util.Scanner;

public class Main {

    public static void printMatrixBySpin(int[][] matrix) {
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            printEdge(matrix, tR++, tC++, dR--, dC--);
        }
    }

    public static void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                System.out.print(matrix[tR][i] + " ");
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                System.out.print(matrix[i][tC] + " ");
            }
        } else {
            int curR = tR;
            int curC = tC;
            while (curC != dC) {
                System.out.print(matrix[tR][curC++] + " ");
            }
            while (curR != dR) {
                System.out.print(matrix[curR++][dC] + " ");
            }
            while (curC != tC) {
                System.out.print(matrix[dR][curC--] + " ");
            }
            while (curR != tR) {
                System.out.print(matrix[curR--][tC] + " ");
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        printMatrixBySpin(matrix);
    }
}
发表于 2019-10-28 11:10:36 回复(0)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        int matrix[][] = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                matrix[i][j] = scanner.nextInt();
            }
        }
        
        int startR=0,startC=0,endR=n-1,endC=m-1;
        while(startR<=endR && startC<=endC){
            if(startR==endR){
                for(int j=startC;j<=endC;j++){
                    System.out.print(matrix[startR][j] + " ");
                }
            }else if(startC == endC){
                for(int i=startR;i<=endR;i++){
                    System.out.print(matrix[i][startR] + " ");
                }
            }else{
                int p=startC;
                while(p<=endC){
                    System.out.print(matrix[startR][p] + " ");
                    p++;
                }
                p = startR+1;
                while(p<=endR){
                    System.out.print(matrix[p][endC] + " ");
                    p++;
                }
                p = endC-1;
                while(p>=startC){
                    System.out.print(matrix[endR][p] + " ");
                    p--;
                }
                p = endR - 1;
                while(p>startR){
                    System.out.print(matrix[p][startC] + " ");
                    p--;
                }
                
            }
            
            
            startR++;
            startC++;
            endR--;
            endC--;
        }
	}
}

发表于 2019-10-17 13:28:44 回复(0)
import java.util.Scanner;

public class Main {

	public static void spiralOrderPrint(int[][] matrix) {
		int tR = 0;
		int tC = 0;
		int dR = matrix.length - 1;
		int dC = matrix[0].length - 1;
		while (tR <= dR && tC <= dC) {
			printEdge(matrix, tR++, tC++, dR--, dC--);
		}
	}

	public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
		if (tR == dR) {
			for (int i = tC; i <= dC; i++) {
				System.out.print(m[tR][i] + " ");
			}
		} else if (tC == dC) {
			for (int i = tR; i <= dR; i++) {
				System.out.print(m[i][tC] + " ");
			}
		} else {
			int curC = tC;
			int curR = tR;
			while (curC != dC) {
				System.out.print(m[tR][curC] + " ");
				curC++;
			}
			while (curR != dR) {
				System.out.print(m[curR][dC] + " ");
				curR++;
			}
			while (curC != tC) {
				System.out.print(m[dR][curC] + " ");
				curC--;
			}
			while (curR != tR) {
				System.out.print(m[curR][tC] + " ");
				curR--;
			}
		}
	}

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String[] size = firstLine.split(" ");
        int n = Integer.valueOf(size[0]);
        int m = Integer.valueOf(size[1]);
        int[][] matrix = new int[n][m];
        
        for(int i=0; i<n; i++){
            String line = sc.nextLine();
            String[] array = line.split(" ");
            for(int j=0; j<m; j++){
                matrix[i][j] = Integer.valueOf(array[j]);
            }
        }
        
		spiralOrderPrint(matrix);

	}

}

发表于 2022-05-25 16:21:24 回复(0)
def spiralOrderPrint(matrix, res):
    tR = 0 # 左上角的行
    tC = 0 # 左上角的列
    dR = len(matrix) - 1   # 右下角的行
    dC = len(matrix[0]) -1 # 右下角的列
    while tR <= dR and tC <= dC:
        printEdge(matrix, tR, tC, dR, dC, res)
        tR += 1
        tC += 1
        dR -= 1
        dC -= 1
    return res

def printEdge(matrix, tR, tC, dR, dC, res):
    if tR == dR:
        # 当矩阵只有一行的时候
        for i in range(tC, dC+1):
            res.append(matrix[tR][i])
    # 当矩阵只有一列的时候
    elif tC == dC:
        for i in range(tR, dR+1):
            res.append(matrix[i][tC])
    else:
        curC = tC
        curR = tR
        while curC != dC:
            res.append(matrix[tR][curC])
            curC += 1
        while curR != dR:
            res.append(matrix[curR][dC])
            curR += 1
        while curC != tC:
            res.append(matrix[dR][curC])
            curC -= 1
        while curR != tR:
            res.append(matrix[curR][tC])
            curR -= 1

if __name__ == '__main__':
    import sys
    n, m = list(map(int, sys.stdin.readline().split()))
    i = 0
    matrix = []
    while i < n:
        matrix.append(list(map(int, sys.stdin.readline().split())))
        i+=1
    res = []
    res1 = spiralOrderPrint(matrix, res)
    res2 = ''
    for i in res1:
        res2 += str(i)+' '
    print(res2)
        

发表于 2021-09-07 09:15:51 回复(0)
#include<bits/stdc++.h>
using namespace std;
void print(vector<vector<int>>& v,int tR,int tC,int dR,int dC)
{
    if(tR==dR)
    {
        for(int i=tC;i<=dC;++i)
            cout<<v[tR][i]<<" ";
    }
    else if(tC==dC)
    {
        for(int j=tR;j<=dR;++j)
            cout<<v[j][tC]<<" ";
    }
    else
    {
        int x = tR;
        int y = tC;
        while(y<dC)
        {
            cout<<v[x][y++]<<" ";
        }
        while(x<dR)
        {
            cout<<v[x++][y]<<" ";
        }
        while(y>tC)
        {
            cout<<v[x][y--]<<" ";
        }
        while(x>tR)
        {
            cout<<v[x--][y]<<" ";
        }
    }

}
int main()
{
    int m,n;
    cin>>m>>n;
    vector<vector<int>>v(m,vector<int>(n,0));
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            cin>>v[i][j];
    int tR = 0;
    int tC = 0;
    int dR = v.size()-1;
    int dC = v[0].size()-1;
    while(tR<=dR && tC<=dC)
        print(v,tR++,tC++,dR--,dC--);

    return 0;
}
发表于 2020-02-08 11:37:06 回复(0)