You can use dynamic programming for this.
(If you have no idea about it, read it on
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg ).
Maintain array dp[3][3][7]. Let the keypad be key[3][3]
dp[i][j][k] -> i,j: indices to identify number, k:how many numbers of length
k+1 possible from key[i][j].
Initialize dp elements to zero.
Make all dp[i][j][0] = 1
Now, dp goes like this.
for ( k = 1; k < 7; ++k )
for ( i=0; i<3; ++i )
for( j=0; j<3; ++j )
for ( m= -2; m<=2; ++m )
if ( m != 0 && (0<=i+m<=2) && (0<=j+m<=2) )
dp[i][j][k] += dp[i+m][j+m][k-1];
For other chess pieces, change the dp logic (After j loop).
~Vishal
On 12/24/06, BoBo_C <[EMAIL PROTECTED]> wrote:
Hi-
I recently ran across a programming problem that I didn't even know how
to begin to solve. I'm just now learning algorithms, and I imagine
some type of algorithm is required. The problem is as follows:
You are given a phone dial pad that looks like this:
1 2 3
4 5 6
7 8 9
Supposing that you're using a bishop (from chess) to dial numbers, and
the bishop can only move like a bishop (that is, diagonally in any
direction for any number of spaces), how many unique seven-digit
numbers can be traced? N.B. - The number '1' is to be disregarded for
the purposes of the problem - it isn't to be included in any numbers.
For example, the bishop starting on '2' could travel thusly:
2-4-2-4-8-6-8. That would account for one possible number. It could
also go 2-4-2-4-2-4-2, etc. If it were on 3, it could go
3-7-5-3-5-9-5.
Another twist is that the design of the solution should enable you to
easily substitute any other type of chess piece for the bishop, adding
an object-oriented aspect to the problem. One number a rook, should you
choose to use it, would be able to dial would be 7-2-7-2-7-2-7. It
would be limited to moving as a rook does in chess.
How would one approach solving this problem?
Thanks for any advice/help/comments...
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
