Created
April 20, 2016 00:11
-
-
Save jianminchen/63c0bccec2ab476d71abbe43c8837566 to your computer and use it in GitHub Desktop.
K Index - using Queue - Julia's practice on April 19, 2016
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 kIndex | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
int k = Convert.ToInt16(Console.ReadLine()); | |
int[][] arr = new int[k][]; | |
for (int i = 0; i < k; i++) | |
arr[i] = new int[k]; | |
for (int i = 0; i < k; i++) | |
{ | |
string s = Console.ReadLine(); | |
string[] aA = s.Split(' '); | |
if (aA.Length != k) | |
return; | |
for (int j = 0; j < k; j++) | |
arr[i][j] = Convert.ToInt16(aA[j].Trim()); | |
} | |
int kIndex = Convert.ToInt16(Console.ReadLine()); | |
if (kIndexFunc(arr, kIndex)) | |
{ | |
Console.WriteLine("YES"); | |
} | |
else | |
Console.WriteLine("NO"); | |
} | |
public static bool kIndexFunc(int[][] arr, int kIndex) | |
{ | |
if (arr == null) return false; | |
int m = arr.Length; | |
int n = arr[0].Length; | |
if (m != n) | |
return false; | |
for (int i = 0; i < m; i++) | |
for (int j = 0; j < m; j++) | |
{ | |
int search = arr[i][j]; | |
if (searchInKIndex(arr, i, j, kIndex, search, m)) | |
return true; | |
} | |
return false; | |
} | |
private static bool searchInKIndex(int[][] arr, int row, int col, int kIndex, int search, int MaxRow) | |
{ | |
bool[][] searchedA = new bool[MaxRow][]; | |
for (int i = 0; i < MaxRow; i++) | |
searchedA[i] = new bool[MaxRow]; | |
for (int i = 0; i < MaxRow; i++) | |
for (int j = 0; j < MaxRow; j++) | |
searchedA[i][j] = false; | |
// up, down, left, right | |
return searchUsingQueue(arr, row, col, row, col, kIndex, search, MaxRow, searchedA); | |
} | |
/* | |
* April 19, 2016 | |
* Two dimension array arr[,], use getLength(0) and getLength(1) for first and second dimension length; | |
* But, jagged array - arr[][], getLength(1) will throw exception - | |
*/ | |
private static bool searchUsingQueue(int[][] arr, int oriX, int oriY, int row, int col, int kIndex, int search, int MaxRow, bool[][] searchedA) | |
{ | |
int rows = arr.GetLength(0); | |
int cols = arr[0].Length; | |
if (!isValid(row, MaxRow) || !isValid(col, MaxRow) || kIndex < 0) | |
return false; | |
Queue<string> queue = new Queue<string>(); | |
searchedA[row][col] = true; | |
queue.Enqueue(getKey(row, col, kIndex)); | |
while (queue.Count > 0) | |
{ | |
string key = (string)queue.Dequeue(); | |
string[] kA = key.Split(';'); | |
int tmpX = Convert.ToInt32(kA[0]); | |
int tmpY = Convert.ToInt32(kA[1]); | |
int indexCount = Convert.ToInt32(kA[2]); | |
if (notSame(tmpX, tmpY, oriX, oriY) && arr[tmpX][tmpY] == arr[oriX][oriY]) | |
return true; | |
if (indexCount > 0) | |
{ | |
int newCount = indexCount - 1; | |
int[][] neighbors = new int[4][]{ | |
new int[2]{-1, 0}, | |
new int[2]{0, -1}, | |
new int[2]{1, 0}, | |
new int[2]{0, 1} | |
}; | |
for(int i= 0; i< neighbors.GetLength(0); i++) | |
{ | |
int nX = tmpX + neighbors[i][0]; | |
int nY = tmpY + neighbors[i][1]; | |
//if(isInRange(nX, nY, arr.GetLength(0), arr.GetLength(1)) && searchedA[nX][nY] == false) // arr.GetLength(1) index out of range | |
if (isInRange(nX, nY, rows, cols) && searchedA[nX][nY] == false) | |
{ | |
searchedA[nX][nY] = true; | |
queue.Enqueue(getKey(nX, nY, newCount)); | |
} | |
} | |
} | |
} | |
return false; | |
} | |
private static bool isInRange(int x, int y, int row, int col) | |
{ | |
if (x >= 0 && x < row && y >= 0 && y < col) | |
return true; | |
return false; | |
} | |
private static string getKey(int row, int col, int kIndex) | |
{ | |
return row.ToString() + ";" + col.ToString() + ";" + kIndex.ToString(); | |
} | |
private static bool isValid(int row, int MaxRow) | |
{ | |
if (row >= 0 && row < MaxRow) | |
return true; | |
else | |
return false; | |
} | |
private static bool notSame(int x1, int y1, int x2, int y2) | |
{ | |
return Math.Abs(x1 - x2) + Math.Abs(y1 - y2) > 0; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment