Problem:
TopCoder Problem Statement - BishopMove
Overview:
Count the number of moves it takes for a bishop to move from one square to another on a chess board.
Java Source:
01: /* 02: TopCoder 03: Single Round Match: 628 04: Division: 2 05: Level: 1 06: Points: 250 07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13280 08: */ 09: 10: public class BishopMove { 11: 12: public int howManyMoves(int r1, int c1, int r2, int c2) { 13: 14: // Get the number of rows and columns that the bishop must move. 15: int rowDiff = Math.abs(r2 - r1); 16: int colDiff = Math.abs(c2 - c1); 17: 18: // Check for no moves necessary 19: if ((rowDiff == 0) && (colDiff == 0)) return 0; 20: 21: /* 22: * If the number of rows that change is the same as the number of 23: * columns that change, we can reach it in one move. 24: */ 25: if (rowDiff == colDiff) return 1; 26: 27: /* 28: * If the difference is not a multiple of 2 (i.e. up 1 row, 29: * and over 2) then the square cannot be reached. 30: */ 31: if (((rowDiff - colDiff) % 2) != 0) return -1; 32: 33: // In any other case, the square can be reached in 2. 34: return 2; 35: 36: } 37: }
Notes:
It helps to think in terms of the basic properties of how a Bishop moves. The following three rules are all you need to solve this problem:
- If the change in the number of rows from the starting square to the destination is the same as the change in the number of columns; then the Bishop can reach that square in 1 move.
- From it's starting position, the Bishop can reach any square where the difference in rows minus the difference in columns is an even multiple of 2.
- Any square that can be reached by the Bishop will take at most 2 moves.
This logic is implemented on lines 25, 31, and 34, and respectively.
Add to that a quick check at line 19 to see if any move is even necessary, and you're done.
No comments:
Post a Comment