Spiral Order

Lab Java Advanced 30 points

Read an r×c matrix and print its elements in clockwise spiral order on one line.

Input

r c, then r rows.

Output

One line.

Example

Input

Output

1 2 3 6 9 8 7 4 5

Sample input available Sample output available

Editor

Java

Hints

Keep four boundaries and shrink them after each side.

Check the boundaries again before the bottom row and left column.

Solution explanation

Boundary-shrinking avoids a separate visited array.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt(), c = sc.nextInt();
        int[][] m = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                m[i][j] = sc.nextInt();
            }
        }
        StringBuilder sb = new StringBuilder();
        int top = 0, bottom = r - 1, left = 0, right = c - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) sb.append(m[top][j]).append(' ');
            top++;
            for (int i = top; i <= bottom; i++) sb.append(m[i][right]).append(' ');
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) sb.append(m[bottom][j]).append(' ');
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) sb.append(m[i][left]).append(' ');
                left++;
            }
        }
        System.out.println(sb.toString().trim());
    }
}

Output

Answer