Created
April 15, 2016 01:10
-
-
Save jianminchen/4d719488e378aeb498d4cb363cbd1f7d to your computer and use it in GitHub Desktop.
Rotate Array k steps - run time error - https://www.hackerrank.com/challenges/matrix-rotation-algo
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 | |
{ | |
static void Main(string[] args) | |
{ | |
string s1 = Console.ReadLine(); | |
string[] sA = s1.Split(' '); | |
int row = Convert.ToInt16(sA[0].Trim()); | |
int col = Convert.ToInt16(sA[1].Trim()); | |
int T = Convert.ToInt16(sA[2].Trim()); | |
int[][] arr = new int[row][]; | |
for (int i = 0; i < row; i++) | |
arr[i] = new int[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()); | |
} | |
for (int i = 0; i < T; i++) | |
rotateArrayOneStepAntiClockwise(arr); | |
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 it in place | |
*/ | |
public static bool rotateArrayOneStepAntiClockwise(int[][] arr) | |
{ | |
if (arr == null) return false; | |
int row = arr.Length; // row | |
int col = arr[0].Length; // column | |
int start = 0; | |
int end = col - 1; | |
while (start <= end && start < row / 2 && start < col / 2) | |
{ | |
int totalRow = row - 2 * start; | |
int totalCols = col - 2 * start; | |
int firstRow = start; | |
//int LastRow = totalRow - 1; // math is wrong for last row | |
int lastRow = row - start - 1; | |
int firstCol = start; | |
int lastCol = end; | |
int totalSwap = 2 * (totalRow + totalCols) - 4 - 1; | |
swap(arr, start, start, start + 1, start, row, col); | |
totalSwap--; | |
// for up row Direction: L -> R | |
for (int i = firstCol + 1; i <= lastCol; i++, totalSwap--) | |
{ | |
int[] node = new int[2] { firstRow, i }; | |
int[] node2 = new int[2] { firstRow, i - 1 }; // left node | |
swap(arr, node[0], node[1], node2[0], node2[1], row, col); | |
} | |
// for right column Direction: top -> down | |
for (int i = firstRow + 1; i <= lastRow; i++, totalSwap--) | |
{ | |
int[] node = new int[2] { i, lastCol }; | |
int[] node2 = new int[2] { i - 1, lastCol }; // up node | |
swap(arr, node[0], node[1], node2[0], node2[1], row, col); | |
} | |
// for down row - Direction: R -> L | |
for (int i = lastCol; i > firstCol && totalSwap>=0; i--, totalSwap--) | |
{ | |
int[] node = new int[2] { lastRow, i }; | |
int[] node2 = new int[2] { lastRow, i - 1 }; // left node | |
if(isSameNode(node2, start, start) || isSameNode(node2, start+1, start)) | |
break; | |
swap(arr, node[0], node[1], node2[0], node2[1], row, col); | |
} | |
// for left column - Direction: Down -> up first 2 rows - no touch | |
for (int i = lastRow; i >= firstRow + 3 && totalSwap>=0; i--, totalSwap--) // | |
{ | |
int[] node = new int[2] { i, firstCol }; | |
int[] node2 = new int[2] { i - 1, firstCol }; // up node | |
swap(arr, node[0], node[1], node2[0], node2[1], row, col); | |
} | |
start++; | |
end--; | |
} | |
return true; | |
} | |
/* | |
* | |
*/ | |
private static bool isSameNode(int[] node, int x, int y) | |
{ | |
return Math.Abs(node[0] - x) + Math.Abs(node[1] - y) == 0; | |
} | |
private static void swap(int[][] arr, int x1, int y1, int x2, int y2, int maxRow, int maxCol) | |
{ | |
if (!(x1 < maxRow && y1 < maxCol && x2 < maxRow && y2 < maxCol)) | |
return; | |
if (!(x1 >= 0 && y1 >= 0 && x2 >= 0 && y2 >= 0)) | |
return; | |
int tmp = arr[x1][y1]; | |
arr[x1][y1] = arr[x2][y2]; | |
arr[x2][y2] = tmp; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment