Print a given matrix in spiral using DFS

To solve the problem follow the below idea:

Another recursive approach is to consider DFS movement within the matrix (right->down->left->up->right->..->end). We do this by modifying the matrix itself such that when DFS algorithm visits each matrix cell it’s changed to a value which cannot be contained within the matrix. The DFS algorithm is terminated when it visits a cell such that all of its surrounding cells are already visited. The direction of the DFS search is controlled by a variable.

Follow the given steps to solve the problem:

create a DFS function that takes matrix, cell indices, and direction
checks are cell indices pointing to a valid cell (that is, not visited and in bounds)? if not, skip this cell
print cell value
mark matrix cell pointed by indicates as visited by changing it to a value not supported in the matrix
check are surrounding cells valid? if not stop the algorithm, else continue
if the direction is given right then check, if the cell to the right is valid. if so, DFS to the right cell given the steps above, else, change the direction to down and DFS downwards given the steps above
else, if the direction given is down then check, if the cell to the down is valid. if so, DFS to the cell below given the steps above, else, change the direction to left and DFS leftwards given the steps above
else, if the direction given is left then check, if the cell to the left is valid. if so, DFS to the left cell given the steps above, else, change the direction to up and DFS upwards given the steps above
else, if the direction given is up then check, if the cell to the up is valid. if so, DFS to the upper cell given the steps above, else, change the direction to right and DFS rightwards given the steps above

Below is an implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
 
bool isInBounds(int i, int j)
{
    if (i < 0 || i >= R || j < 0 || j >= C)
        return false;
    return true;
}
 
// check if the position is blocked
bool isBlocked(int matrix[R][C], int i, int j)
{
    if (!isInBounds(i, j))
        return true;
    if (matrix[i][j] == -1)
        return true;
    return false;
}
 
// DFS code to traverse spirally
void spirallyDFSTraverse(int matrix[R][C], int i, int j,
                          int dir, vector<int>& res)
{
    if (isBlocked(matrix, i, j))
        return;
    bool allBlocked = true;
    for (int k = -1; k <= 1; k += 2) {
        allBlocked = allBlocked
                     && isBlocked(matrix, k + i, j)
                     && isBlocked(matrix, i, j + k);
    }
    res.push_back(matrix[i][j]);
    matrix[i][j] = -1;
    if (allBlocked) {
        return;
    }
 
    // dir: 0 - right, 1 - down, 2 - left, 3 - up
    int nxt_i = i;
    int nxt_j = j;
    int nxt_dir = dir;
    if (dir == 0) {
        if (!isBlocked(matrix, i, j + 1)) {
            nxt_j++;
        }
        else {
            nxt_dir = 1;
            nxt_i++;
        }
    }
    else if (dir == 1) {
        if (!isBlocked(matrix, i + 1, j)) {
            nxt_i++;
        }
        else {
            nxt_dir = 2;
            nxt_j--;
        }
    }
    else if (dir == 2) {
        if (!isBlocked(matrix, i, j - 1)) {
            nxt_j--;
        }
        else {
            nxt_dir = 3;
            nxt_i--;
        }
    }
    else if (dir == 3) {
        if (!isBlocked(matrix, i - 1, j)) {
            nxt_i--;
        }
        else {
            nxt_dir = 0;
            nxt_j++;
        }
    }
    spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir,
                         res);
}
 
// To traverse spirally
vector<int> spirallyTraverse(int matrix[R][C])
{
    vector<int> res;
    spirallyDFSTravserse(matrix, 0, 0, 0, res);
    return res;
}
 
// Driver Code
int main()
{
    int a[R][C] = { { 1, 2, 3, 4 },
                    { 5, 6, 7, 8 },
                    { 9, 10, 11, 12 },
                    { 13, 14, 15, 16 } };
 
    // Function Call
    vector<int> res = spirallyTraverse(a);
    int size = res.size();
    for (int i = 0; i < size; ++i)
        cout << res[i] << " ";
    cout << endl;
    return 0;
} // code contributed by Ephi F

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
    public static int R = 4, C = 4;
    public static boolean isInBounds(int i, int j)
    {
        if (i < 0 || i >= R || j < 0 || j >= C)
            return false;
        return true;
    }
 
    // check if the position is blocked
    public static boolean isBlocked(int[][] matrix, int i,
                                    int j)
    {
        if (!isInBounds(i, j))
            return true;
        if (matrix[i][j] == -1)
            return true;
        return false;
    }
 
    // DFS code to traverse spirally
    public static void
    spirallyDFSTraverse(int[][] matrix, int i, int j,
                         int dir, ArrayList<Integer> res)
    {
        if (isBlocked(matrix, i, j))
            return;
        boolean allBlocked = true;
        for (int k = -1; k <= 1; k += 2) {
            allBlocked = allBlocked
                         && isBlocked(matrix, k + i, j)
                         && isBlocked(matrix, i, j + k);
        }
        res.add(matrix[i][j]);
        matrix[i][j] = -1;
        if (allBlocked) {
            return;
        }
 
        // dir: 0 - right, 1 - down, 2 - left, 3 - up
        int nxt_i = i;
        int nxt_j = j;
        int nxt_dir = dir;
        if (dir == 0) {
            if (!isBlocked(matrix, i, j + 1)) {
                nxt_j++;
            }
            else {
                nxt_dir = 1;
                nxt_i++;
            }
        }
        else if (dir == 1) {
            if (!isBlocked(matrix, i + 1, j)) {
                nxt_i++;
            }
            else {
                nxt_dir = 2;
                nxt_j--;
            }
        }
        else if (dir == 2) {
            if (!isBlocked(matrix, i, j - 1)) {
                nxt_j--;
            }
            else {
                nxt_dir = 3;
                nxt_i--;
            }
        }
        else if (dir == 3) {
            if (!isBlocked(matrix, i - 1, j)) {
                nxt_i--;
            }
            else {
                nxt_dir = 0;
                nxt_j++;
            }
        }
        spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir,
                             res);
    }
 
    // to traverse spirally
    public static ArrayList<Integer>
    spirallyTraverse(int[][] matrix)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        spirallyDFSTravserse(matrix, 0, 0, 0, res);
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[][] = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
 
        // Function Call
        ArrayList<Integer> res = spirallyTraverse(a);
        int size = res.size();
        for (int i = 0; i < size; ++i)
            System.out.print(res.get(i) + " ");
        System.out.println();
    }
}
 
// This code is contributed by Manu Pathria

Python3

# Python3 program for the above approach
 
R = 4
C = 4
 
 
def isInBounds(i, j):
    global R
    global C
    if (i < 0 or i >= R or j < 0 or j >= C):
        return False
    return True
 
# Check if the position is blocked
 
 
def isBlocked(matrix, i, j):
    if (not isInBounds(i, j)):
        return True
    if (matrix[i][j] == -1):
        return True
 
    return False
 
# DFS code to traverse spirally
 
 
def spirallyDFSTraverse(matrix, i, j, Dir, res):
    if (isBlocked(matrix, i, j)):
        return
 
    allBlocked = True
    for k in range(-1, 2, 2):
        allBlocked = allBlocked and isBlocked(
            matrix, k + i, j) and isBlocked(matrix, i, j + k)
 
    res.append(matrix[i][j])
    matrix[i][j] = -1
    if (allBlocked):
        return
 
    # dir: 0 - right, 1 - down, 2 - left, 3 - up
    nxt_i = i
    nxt_j = j
    nxt_dir = Dir
    if (Dir == 0):
        if (not isBlocked(matrix, i, j + 1)):
            nxt_j += 1
        else:
            nxt_dir = 1
            nxt_i += 1
 
    elif(Dir == 1):
        if (not isBlocked(matrix, i + 1, j)):
            nxt_i += 1
        else:
            nxt_dir = 2
            nxt_j -= 1
 
    elif(Dir == 2):
        if (not isBlocked(matrix, i, j - 1)):
            nxt_j -= 1
        else:
            nxt_dir = 3
            nxt_i -= 1
 
    elif(Dir == 3):
        if (not isBlocked(matrix, i - 1, j)):
            nxt_i -= 1
        else:
            nxt_dir = 0
            nxt_j += 1
 
    spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir, res)
 
# To traverse spirally
 
 
def spirallyTraverse(matrix):
    res = []
    spirallyDFSTravserse(matrix, 0, 0, 0, res)
    return res
 
 
# Driver code
if __name__ == "__main__":
    a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
 
    # Function Call
    res = spirallyTraverse(a)
    print(*res)
 
# This code is contributed by rag2127

C#

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG {
 
    public static int R = 4, C = 4;
    public static bool isInBounds(int i, int j)
    {
        if (i < 0 || i >= R || j < 0 || j >= C)
            return false;
 
        return true;
    }
 
    // Check if the position is blocked
    public static bool isBlocked(int[, ] matrix, int i,
                                 int j)
    {
        if (!isInBounds(i, j))
            return true;
        if (matrix[i, j] == -1)
            return true;
        return false;
    }
 
    // DFS code to traverse spirally
    public static void spirallyDFSTraverse(int[, ] matrix,
                                            int i, int j,
                                            int dir,
                                            List<int> res)
    {
        if (isBlocked(matrix, i, j))
            return;
 
        bool allBlocked = true;
 
        for (int k = -1; k <= 1; k += 2) {
            allBlocked = allBlocked
                         && isBlocked(matrix, k + i, j)
                         && isBlocked(matrix, i, j + k);
        }
        res.Add(matrix[i, j]);
        matrix[i, j] = -1;
 
        if (allBlocked) {
            return;
        }
 
        // dir: 0 - right, 1 - down, 2 - left, 3 - up
        int nxt_i = i;
        int nxt_j = j;
        int nxt_dir = dir;
        if (dir == 0) {
            if (!isBlocked(matrix, i, j + 1)) {
                nxt_j++;
            }
            else {
                nxt_dir = 1;
                nxt_i++;
            }
        }
        else if (dir == 1) {
            if (!isBlocked(matrix, i + 1, j)) {
                nxt_i++;
            }
            else {
                nxt_dir = 2;
                nxt_j--;
            }
        }
        else if (dir == 2) {
            if (!isBlocked(matrix, i, j - 1)) {
                nxt_j--;
            }
            else {
                nxt_dir = 3;
                nxt_i--;
            }
        }
        else if (dir == 3) {
            if (!isBlocked(matrix, i - 1, j)) {
                nxt_i--;
            }
            else {
                nxt_dir = 0;
                nxt_j++;
            }
        }
        spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir,
                             res);
    }
 
    // To traverse spirally
    public static List<int> spirallyTraverse(int[, ] matrix)
    {
        List<int> res = new List<int>();
        spirallyDFSTravserse(matrix, 0, 0, 0, res);
        return res;
    }
 
    // Driver code
    static public void Main()
    {
        int[, ] a = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
 
        // Function Call
        List<int> res = spirallyTraverse(a);
        int size = res.Count;
 
        for (int i = 0; i < size; ++i)
            Console.Write(res[i] + " ");
 
        Console.WriteLine();
    }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
 
var R = 4, C = 4;
function isInBounds(i, j)
{
    if (i < 0 || i >= R || j < 0 || j >= C)
        return false;
    return true;
}
// Check if the position is blocked
function isBlocked(matrix, i, j)
{
    if (!isInBounds(i, j))
        return true;
    if (matrix[i][j] == -1)
        return true;
    return false;
}
// DFS code to traverse spirally
function spirallyDFSTraverse(matrix, i, j, dir, res)
{
    if (isBlocked(matrix, i, j))
        return;
    var allBlocked = true;
    for (var k = -1; k <= 1; k += 2) {
        allBlocked = allBlocked
                     && isBlocked(matrix, k + i, j)
                     && isBlocked(matrix, i, j + k);
    }
    res.push(matrix[i][j]);
    matrix[i][j] = -1;
    if (allBlocked) {
        return;
    }
    // dir: 0 - right, 1 - down, 2 - left, 3 - up
    var nxt_i = i;
    var nxt_j = j;
    var nxt_dir = dir;
    if (dir == 0) {
        if (!isBlocked(matrix, i, j + 1)) {
            nxt_j++;
        }
        else {
            nxt_dir = 1;
            nxt_i++;
        }
    }
    else if (dir == 1) {
        if (!isBlocked(matrix, i + 1, j)) {
            nxt_i++;
        }
        else {
            nxt_dir = 2;
            nxt_j--;
        }
    }
    else if (dir == 2) {
        if (!isBlocked(matrix, i, j - 1)) {
            nxt_j--;
        }
        else {
            nxt_dir = 3;
            nxt_i--;
        }
    }
    else if (dir == 3) {
        if (!isBlocked(matrix, i - 1, j)) {
            nxt_i--;
        }
        else {
            nxt_dir = 0;
            nxt_j++;
        }
    }
    spirallyDFSTravserse(matrix, nxt_i, nxt_j, nxt_dir,
                         res);
}
// To traverse spirally
function spirallyTraverse(matrix)
{
    var res = [];
    spirallyDFSTravserse(matrix, 0, 0, 0, res);
    return res;
}
// Driver code
var a = [ [ 1, 2, 3, 4 ],
              [ 5, 6, 7, 8 ],
              [ 9, 10, 11, 12 ],
              [ 13, 14, 15, 16 ]];
// Function Call
var res = spirallyTraverse(a);
var size = res.length;
for (var i = 0; i < size; ++i)
    document.write(res[i] + " ");
 
</script>

Output

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

Time Complexity: O(M*N). To traverse the matrix O(M*N) time is required.
Auxiliary Space: O(1). No extra space is required (without consideration of the stack used by the recursion).

Please write comments if you find the above code incorrect, or find other ways to solve the same problem.

Print a given matrix in spiral using DFS

C++

Java

Python3

C#

Javascript

Print a given matrix in spiral form

Categories

Contact US

Print a given matrix in spiral using DFS

C++

Java

Python3

C#

Javascript

Print a given matrix in spiral form

Similar Reads

Categories

Contact US