## Friday, June 27, 2008

### Top Coder SRM 701

Problem Statement
You are playing a game where you must traverse a rectangular grid of cells using a spiral path. The map is given in a String[] levelMap, where the j-th character of the i-th element is the number of points associated with the cell in row i, column j. Rows are numbered from top to bottom, starting at 0, and columns are numbered from left to right, starting at 0. All coordinates in this problem will be given as (row, column). You start at cell (0,0), the top left corner of the grid. You are facing right. You move by repeating the following strategy until you have visited every single cell on the grid exactly once. If there is an adjacent cell in front of you that you haven't visited yet, move forward to that cell. Otherwise, if there are still unvisited cells on the grid, turn 90 degrees clockwise. To calculate your final score, add up all the points for the cells that you visited, but don't include the cells in which you changed direction. The first and last cells in your path will always be included in your final score. See examples for further clarification.
Definition
Class:
SpiralWalking
Method:
totalPoints
Parameters:
String[]
Returns:
int
Method signature:
int totalPoints(String[] levelMap)
(be sure your method is public)

Constraints
-
levelMap will contain between 2 and 50 elements, inclusive.
-
All elements of levelMap will contain the same number of characters.
-
Each element of levelMap will contain between 2 and 50 digits ('0'-'9'), inclusive.
Examples
0)

{"111",
"111",
"111"}
Returns: 5
This is the spiral path you must follow: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (1,1).
1)

{"101",
"110"}
Returns: 3
The grid is not always a square.
2)

{"00",
"10"}
Returns: 1

3)

{"86850",

`   1: public class SpiralWalking{`
`   2: public int totalPoints(String[] levelMap){`
`   3:       int[] pos={0,0};`
`   4:       int dim=0;`
`   5:       int ymax=levelMap.length;`
`   6:       int xmax=levelMap.length();`
`   7:       int cells=(ymax)*(xmax);`
`   8:       int[] size={xmax,ymax};`
`   9:       boolean isForward=true;`
`  10:       boolean[][] isDone=new boolean[xmax][ymax]; `
`  11:       int score=0;`
`  12:       isDone=true;`
`  13:       int modCounter=0;`
`  14:      for(int count=1;count<cells;count++){`
`  15:           if(pos[dim]==size[dim]-1 || (pos[dim]==0 && count!=1)`
`  16:                   || ((isForward && dim==0 && isDone[pos+1][pos]) `
`  17:                           || (isForward && dim==1 && isDone[pos][pos+1]))`
`  18:                                   || ((!isForward && dim==0 && isDone[pos-1][pos]) `
`  19:                                           || (!isForward && dim==1 && isDone[pos][pos-1])))  {`
`  20:           if(++modCounter%2==0) isForward=!isForward;`
`  21:           dim=++dim%2;`
`  22:           if(isForward)pos[dim]++; else pos[dim]--;`
`  23:           isDone[pos][pos]=true;`
`  24:           }else {`
`  25:               score+=Integer.parseInt(String.valueOf(levelMap[pos].charAt(pos)));`
`  26:               if(isForward)pos[dim]++; else pos[dim]--;`
`  27:               isDone[pos][pos]=true;`
`  28:           }`
`  29:       }`
`  30:       score+=Integer.parseInt(String.valueOf(levelMap[pos].charAt(pos)));`
`  31:       return score;`
`  32: }`
`  33:  `
`  34: public static void main(String z[]){`
`  35:     String[] inp={"86850","76439",`
`  36:             "15863",`
`  37:             "24568",`
`  38:             "45679",`
`  39:             "71452",`
`  40:             "05483"`
`  41:             };`
`  42:     System.out.println(new SpiralWalking().totalPoints(inp));`
`  43: }`
`  44: }`

"76439",
"15863",
"24568",
"45679",
"71452",
"05483"}
Returns: 142
The following image shows your path. The yellow cell is the last cell you visit. You receive points for all the cells except the red ones.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.