Spiral Walking

Problem: Spiral Walking

Description: The problem is to traverse a rectangular grid of cells, starting from the top first cell on the left. Initially, you start in the "right" direction and move through the grid, cell by cell. Each and every cell must be visited only once. If you end up in a cell, which is the last in that direction (or already visited), change direction and move forward. This should be done til you cover all the cells in that rectangular grid.

Example: (for a 4*3 grid)

- - >
^ > |
| v |
< - v

Java Solution: In this solution, I'm using direction flags and a boolean matrix (to identify if a cell has been already visited or not) and returning a string[][] array of the resulting spiral path. I've not optimised the code for clarity and other reasons. Please feel free to comment/suggest with any other ideas or positive criticism. The Java implementation is as below:



Since each and every cell has to be visited, this algo might be slow for large input values. But for this Java implementation, I've used 'int' for 'row' and 'col'. So, you cant specify large input values anyways, although it still matters.

The code above outputs the following string[][] array, when provided with an input of 10 rows and 10 columns:

- - - - - - - - - >
^ - - - - - - - > |
| ^ - - - - - > | |
| | ^ - - - > | | |
| | | ^ - > | | | |
| | | | < v | | | |
| | | < - - v | | |
| | < - - - - v | |
| < - - - - - - v |
< - - - - - - - - v

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.