1. Introduction
The "Shift Matrix" problem is a fascinating array manipulation challenge that requires shifting all elements of a matrix by one position in a spiral order. It's a unique problem that tests a developer's ability to implement complex matrix traversal and modification techniques, often seen in advanced programming scenarios.
Problem
Given an M × N integer matrix, the task is to shift all its elements by one position in a spiral order. The spiral order means moving along the matrix in a clockwise spiral, and wrapping the last element to the first position.
2. Solution Steps
1. Extract the elements of the matrix in a spiral order and store them in an array.
2. Perform a right circular shift on this array by one position.
3. Refill the matrix with the shifted elements, placing them back in spiral order.
3. Code Program
#include <iostream>
#include <vector>
using namespace std;
// Function to extract the elements of a matrix in spiral order
vector<int> getSpiralOrder(const vector<vector<int>>& matrix) {
vector<int> result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
// Traverse from left to right
for (int i = left; i <= right; i++) result.push_back(matrix[top][i]);
top++;
// Traverse downwards
for (int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
right--;
// Check if top or left become out of bounds
if (!(top <= bottom && left <= right)) break;
// Traverse from right to left
for (int i = right; i >= left; i--) result.push_back(matrix[bottom][i]);
bottom--;
// Traverse upwards
for (int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
left++;
}
return result;
}
// Function to shift the matrix in spiral order
void shiftSpiralMatrix(vector<vector<int>>& matrix) {
vector<int> spiralOrder = getSpiralOrder(matrix);
// Perform a circular shift
spiralOrder.insert(spiralOrder.begin(), spiralOrder.back());
spiralOrder.pop_back();
// Refill the matrix in spiral order
int index = 0, m = matrix.size(), n = matrix[0].size();
int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// Refill from left to right
for (int i = left; i <= right; i++) matrix[top][i] = spiralOrder[index++];
top++;
// Refill downwards
for (int i = top; i <= bottom; i++) matrix[i][right] = spiralOrder[index++];
right--;
// Check if top or left become out of bounds
if (!(top <= bottom && left <= right)) break;
// Refill from right to left
for (int i = right; i >= left; i--) matrix[bottom][i] = spiralOrder[index++];
bottom--;
// Refill upwards
for (int i = bottom; i >= top; i--) matrix[i][left] = spiralOrder[index++];
left++;
}
}
int main() {
vector<vector<int>> matrix = {
{1, 2, 3, 4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7},
{14, 23, 22, 21, 8},
{13, 12, 11, 10, 9}
};
shiftSpiralMatrix(matrix);
// Print the shifted matrix
for (const auto& row : matrix) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
Output:
25 1 2 3 4
Explanation:
The program first extracts elements from the matrix in a spiral order and stores them in an array.
It then shifts this array to the right by one position, effectively moving the last element to the first position.
Finally, it refills the matrix with these shifted elements, again placing them in a spiral order.
This method provides an elegant solution to the problem, ensuring the matrix is shifted as required while maintaining the integrity of its spiral structure.
Comments
Post a Comment