Saved Bookmarks
| 1. |
Given a 2D matrix with n rows and m columns, your task is to print the elements of the matrix in a zigzag manner as shown in the image below : |
|
Answer» For example, Output: Input: Output: The strategy is straightforward. We will keep iterating over each diagonal element one by one and change the direction based on the previous match. #include<bits/stdc++.h>using namespace std;// function to print the matrix in a zigzag patternvoid zigZagTraversal(VECTOR<vector<int>> arr, int n, int m){ int cur_row = 0, cur_col = 0; //denotes the current row and COLUMN // false denotes cur_col NEEDS to be INCREMENTED, true denotes cur_row needs to be incremented bool flag = false; // Printing matrix of lower half zig-zag pattern int mn = min(m, n); for (int length = 1; length <= mn; ++length) { for (int i = 0; i < length; ++i) { cout << arr[cur_row][cur_col] << " "; if (i + 1 == length) break; // If flag is true we increment cur_row and decrement cur_col else decrement cur_row and increment cur_col if (flag == true){ cur_row = cur_row + 1; cur_col = cur_col - 1; } else{ cur_row = cur_row - 1; cur_col = cur_col + 1; } } if (length == mn) break; // We update cur_row or cur_col value according to the last increment if (flag){ cur_row = cur_row + 1; flag = false; } else{ cur_col = cur_col + 1; flag = true; } } // Updating the indexes of cur_row and cur_col variable if (cur_row == 0) { if (cur_col == m - 1) cur_row = cur_row + 1; else cur_col = cur_col + 1; flag = 1; } else { if (cur_row == n - 1) cur_col = cur_col + 1; else cur_row = cur_row + 1; flag = 0; } // Printing the next half zig-zag pattern int mx = max(m, n) - 1; for (int length, diagonal = mx; diagonal > 0; --diagonal) { if (diagonal > mn) length = mn; else length = diagonal; for (int i = 0; i < length; ++i) { cout << arr[cur_row][cur_col] << " "; if (i + 1 == length) break; // We update cur_row or cur_col value according to the last increment if (flag == true){ cur_row = cur_row + 1; cur_col = cur_col - 1; } else{ cur_col = cur_col + 1; cur_row = cur_row - 1; } } // Updating the cur_row and cur_col variables if (cur_row == 0 || cur_col == m - 1) { if (cur_col == m - 1) cur_row = cur_row + 1; else cur_col = cur_col + 1; flag = true; } else if (cur_col == 0 || cur_row == n - 1) { if (cur_row == n - 1) cur_col = cur_col + 1; else cur_row = cur_row + 1; flag = false; } }} int main(){ vector<vector<int>> arr = vector<vector<int>>(3, vector<int>(3, 0)); for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) arr[i][j] = 3 * i + (j + 1); } zigZagTraversal(arr, 3, 3); return 0;}Explanation: We follow a simulation approach in the above code. First, we print the elements in the first upper half of the matrix. Then, we print the elements of the lower half of the matrix. We iterate each diagonal one by one and print its elements. |
|