DiagonalPath

DiagonalPath:
On a grid, you can make moves up, down, left or right. Given starting position (x1,y1) and destination (x2,y2), you should return the maximum number of times that the movement direction may be changed, to still reach the destination in the minimum number of turns. For instance, given (0,0) and (3,3) you could make the following moves: right,right,right,up,up,up – but the movement direction changes just once. Alternatively, you could make the moves: right, up, right, up, right, up – the movement direction changes 5 times, and you still make the minimum possible number of moves, which is 6.
Constraints: x1,x2,y1,y2 are all between -1,000,000 and +1,000,000 inclusive.

Introduction

Hello, I’m d000hg, and this is my blog. I’m going to use it to talk about anything I find interesting. That means, in nearly all cases, something related to programming or software development. As well as that, articles and algorithmic problems I write will appear here.

As well as here, you can find me on www.gamedev.net and www.topcoder.com/tc

So for this first post, here is a problem I wrote, in a style similar to those found on TopCoder, USACO, etc. Feel free to post ideas, code, bugs, … If you want to discuss this problem on TopCoder’s forums I’m fine with that, we discuss USACO, SPOJ there after all, but please link back to this post.

I have a fair few problems stored up so expect them every couple of days…

I’m new to blogging so any tips about the way I write, or how my blog is set up, are welcome.

2D Palindromes.

A palindrome is a sequence of letters which is the same no matter which way it is read. For instance HANNAH or ABCBA. A 2-dimensional palindrome extends this idea for a table of letters. A section of a table is 2D-palindromic if each row is a palindrome and each column is also a palindrome. For instance:
ABCDEDCBA
BCDEFEDCB
ABCDEDCBA

Here each row is a 9-letter palindrome, and each row a 3-letter palindrome.

Given a string[] grid, where the ith element is the ith row of a character grid, return the area of the largest 2-D palindromic region within this grid.

Examples:
“ABCDEDCBA”,
“BCDEFEDCB”,
“ABCDEDCBA” The whole region is a 2D palindromic so return 9×3 = 27.

“AAAAAAAAAAAAA”,
“AAAAAAAAABBBB”,
“AAAAAAAAABBBB”,
“AAAAAAAAABBBB” There is a 9×4 palindromic region consisting entirely of ‘A’ characters.

Notes:
grid may have between 1 and 50 entries; each entry may have between 1 and 50 upper-case characters A-Z; all entries in grid are the same length.