Spiral Walking

Posted on July 4, 2008


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

Blog Categories
Disclaimer
The views expressed on this blog are my personal views and do not reflect the views of my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.