Created
April 24, 2017 03:18
-
-
Save jianminchen/0011462611ee5eb80b84ec7946c3611a to your computer and use it in GitHub Desktop.
Manhattan 2 - 6 timeout cases - score 25.00 - maximum 50
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 Manhattan2 | |
{ | |
/// <summary> | |
/// https://www.hackerrank.com/contests/booking-womenintech/challenges/manhattan-2 | |
/// The idea is to start from top left node, always go right or down, and then track the | |
/// sum and max value; | |
/// Because the size of matrix is 100 * 100, queue will cause out-of-memory, use stack, DFS | |
/// search, try to use recursive solution if possible | |
/// 200 depth at most, 100 + 100 | |
/// try to get some points first, and then get the idea - 2:35pm | |
/// | |
/// </summary> | |
class Manhattan2 | |
{ | |
internal class Node | |
{ | |
public int Sum { get; set; } | |
public int MaxValue { get; set; } | |
public int candies | |
{ | |
get | |
{ | |
return Sum + SecondsLeft * MaxValue; | |
} | |
} | |
public int SecondsLeft { get; set; } | |
public int startRow { get; set; } | |
public int startCol { get; set; } | |
public int maximumCandies { get; set; } | |
public int seconds {get; set;} | |
} | |
static void Main(string[] args) | |
{ | |
ProcessInput(); | |
} | |
public static void ProcessInput() | |
{ | |
var numbers = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
int rows = numbers[0]; | |
int cols = numbers[1]; | |
int seconds = numbers[2]; | |
var matrix = new int[rows][]; | |
for (int i = 0; i < rows; i++) | |
{ | |
matrix[i] = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
} | |
if (seconds < rows - 1 + cols - 1) | |
{ | |
Console.WriteLine("Too late"); | |
return; | |
} | |
var node = new Node(); | |
node.maximumCandies = int.MinValue; | |
node.startCol = 0; | |
node.startRow = 0; | |
node.seconds = seconds; | |
var maximumCandies = FindRouteFromLeftTopToBottomRight(matrix, node); | |
Console.WriteLine(maximumCandies); | |
} | |
/// <summary> | |
/// Always go two directions | |
/// down or right | |
/// recursive may run to error "stack overflow", using stack instead. | |
/// </summary> | |
/// <param name="matrix"></param> | |
/// <param name="seconds"></param> | |
/// <returns></returns> | |
public static int FindRouteFromLeftTopToBottomRight( | |
int[][] matrix, | |
Node node) | |
{ | |
int rows = matrix.Length; | |
int cols = matrix[0].Length; | |
Stack<Node> stack = new Stack<Node>(); | |
stack.Push(node); | |
int maximumCandies = int.MinValue; | |
while (stack.Count > 0) | |
{ | |
Node visit = stack.Pop(); | |
int startRow = visit.startRow; | |
int startCol = visit.startCol; | |
int seconds = visit.seconds; | |
if (seconds == 0 || isLastNode(startRow, startCol, rows, cols)) | |
{ | |
var current = matrix[startRow][startCol]; | |
var currentMax = visit.MaxValue; | |
visit.Sum += current; | |
visit.SecondsLeft = seconds; | |
visit.MaxValue = (current > currentMax) ? current : currentMax; | |
// calculate candies - if there are extra time, maxValue will be collected multiple times - secondsLeft | |
int currentCandies = visit.candies; | |
maximumCandies = (currentCandies > maximumCandies) ? currentCandies : maximumCandies; | |
continue; | |
} | |
// go to right | |
if (startCol < cols - 1) | |
{ | |
var current = matrix[startRow][startCol]; | |
var currentMax = visit.MaxValue; | |
var nextNode = new Node(); | |
nextNode.Sum = visit.Sum + current; | |
nextNode.MaxValue = (current > currentMax) ? current : currentMax; | |
nextNode.startRow = startRow; | |
nextNode.startCol = startCol + 1; | |
nextNode.seconds = seconds - 1; | |
stack.Push(nextNode); | |
} | |
// go down | |
if (startRow < rows - 1) | |
{ | |
var current = matrix[startRow][startCol]; | |
var currentMax = visit.MaxValue; | |
var nextNode = new Node(); | |
nextNode.Sum = visit.Sum + current; | |
nextNode.MaxValue = (current > currentMax) ? current : currentMax; | |
nextNode.startRow = startRow + 1; | |
nextNode.startCol = startCol; | |
nextNode.seconds = seconds - 1; | |
stack.Push(nextNode); | |
} | |
} | |
return maximumCandies; | |
} | |
/// <summary> | |
/// | |
/// </summary> | |
/// <param name="startRow"></param> | |
/// <param name="startCol"></param> | |
/// <param name="rows"></param> | |
/// <param name="cols"></param> | |
/// <returns></returns> | |
private static bool isLastNode(int startRow, int startCol, int rows, int cols) | |
{ | |
return startRow == (rows - 1) && startCol == (cols - 1); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment