Created
April 19, 2016 01:02
-
-
Save jianminchen/57572227dafe939060f7cc81b193cd9b to your computer and use it in GitHub Desktop.
Matrix Rotation - with bugs to fix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace RotateArray2 | |
{ | |
class Program | |
{ | |
/* | |
* Int16 maximum value is 32676, less than 4 * 10^9 | |
*/ | |
static void Main(string[] args) | |
{ | |
string s1 = Console.ReadLine(); | |
string[] sA = s1.Split(' '); | |
int row = Convert.ToInt32(sA[0].Trim()); | |
int col = Convert.ToInt32(sA[1].Trim()); | |
int T = Convert.ToInt32(sA[2].Trim()); | |
int[,] arr = new int[row, col]; | |
for (int i = 0; i < row; i++) | |
{ | |
string s = Console.ReadLine(); | |
string[] aA = s.Split(' '); | |
if (aA.Length != col) | |
return; | |
for (int j = 0; j < col; j++) | |
// arr[i][j] = Convert.ToInt16(aA[j].Trim()); // Int16 maximum value is 32676, | |
arr[i,j] = Convert.ToInt32(aA[j].Trim()); | |
} | |
rotateArrayOneStepAntiClockwise(arr, T); | |
for (int i = 0; i < row; i++) | |
{ | |
string s = ""; | |
for (int j = 0; j < col; j++) | |
s += arr[i,j].ToString() + " "; | |
Console.WriteLine(s); | |
} | |
} | |
/* | |
* Do not need to do it in place - use extra list to store each loop | |
* | |
*/ | |
public static bool rotateArrayOneStepAntiClockwise(int[,] arr, int cnt) | |
{ | |
if (arr == null) return false; | |
int row = arr.GetLength(0); // row | |
int col = arr.GetLength(1); // column | |
int start = 0; | |
int end = col - 1; | |
while (start <= end && start < row / 2 && start < col / 2) | |
{ | |
int rows = row - 2 * start; | |
int cols = col - 2 * start; | |
int circleLength = 2 * rows + 2 * cols - 4; | |
cnt = cnt % circleLength; | |
for (int ci = 0; ci < cnt; ci++) | |
{ | |
int startR = start; | |
int startC = start; | |
int endR = row - start - 1; | |
int endC = col - start - 1; | |
int tmpVal = arr[startR, startC]; | |
// top row - right to left shift 1 position | |
for (int i = startC; i < endC; i++) | |
arr[startR, i] = arr[startR, i + 1]; | |
// right column - top to down shift 1 position | |
for (int i = startR; i < endR; i++) | |
arr[i, endC] = arr[i +1, endC]; | |
// down row - right to left shift 1 position | |
for (int i = endC; i > startC; i--) | |
arr[endR, i ] = arr[endR, i -1]; | |
// left column - down to up shift 1 position | |
for (int i = endR; i > startR + 1; i--) | |
arr[i, startC] = arr[i - 1, startC]; | |
arr[startR + 1, startC] = tmpVal; | |
} | |
start++; | |
end--; | |
} | |
return true; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Nov. 8, 2016
code review after 7 months
start <= end && start < row / 2 && start < col / 2
start++;
end--;
How many base cases?
22, 23, 32 matrix
22 matrix
1 2
1 2
2*3 matrix
1 2 3
1 2 3
3*2 matrix
1 2
3 4
5 6
R - number of time is rotated.
Go over sample test case, understand the R rotate times - circle