/* ============================================================================
The problem: count the ways to find a word by walking on a grid
You are given a rectangular grid of letters and a word to find.
You must compute the number of ways to find the word within the grid using the following rules:
* start at any cell within the grid
* from there, move to any of the cell’s eight neighboring cells
* continue moving from that neighbor to its neighbors, and so on, until you have spelled out the word
* you may visit cells more than once, but you cannot visit the same cell twice in a row (i.e., you must move for each turn)
Constraints:
* grid will contain between 1 and 50 elements, inclusive.
* Each element of grid will contain between 1 and 50 uppercase (’A’-’Z’) letters, inclusive.
* Each element of grid will contain the same number of characters.
* find will contain between 1 and 50 uppercase (’A’-’Z’) letters, inclusive.
For instance, consider the following grid, taken from the examples in the problem statement:
ABC
FED
GAI
If you were asked to find the word “AEA” on this grid, you could do it in four ways:
1:
*BC ABC *BC
FED F*D FED
GAI GAI GAI
2:
*BC ABC ABC
FED F*D FED
GAI GAI G*I
3:
ABC ABC *BC
FED F*D FED
G*I GAI GAI
4:
ABC ABC ABC
FED F*D FED
G*I GAI G*I
If you were asked to find “ABCD”, you could do it in only one way:
1:
*BC A*C AB* ABC
FED FED FED FE*
GAI GAI GAI GAI
If you were asked to find “AAB”, you could not:
there are no “A” cells on the grid that have other “A” cells as neighbors.
============================================================================ */
/*
* Author : David Tran
* Date : 2008-03-28
*/
using System;
using System.Collections.Generic;
using System.Text;
namespace Quiz
{
class Quiz
{
static void Main(string[] args)
{
new Quiz().Solve();
}
public void Solve()
{
LoadProblem();
foreach (Index index in starts)
{
FindSolution(index.i, index.j, 0);
}
Console.WriteLine("Total Solution = {0}", solutions);
}
struct Index
{
public readonly int i;
public readonly int j;
public Index(int i, int j)
{
this.i = i;
this.j = j;
}
}
int rows;
int cols;
Dictionary<int, List<Index>>[,] grid;
int lastNumber;
List<Index> starts;
int solutions = 0;
private void LoadProblem()
{
// to simplify, we hard-coded the problem data for now.
rows = 3;
cols = 3;
int cellLength = 2;
string[,] gridData = {
{"AA", "BB", "CZ"},
{"FF", "EE", "DD"},
{"GX", "AA", "IY"},
};
string goal = "AAEEAA";
// split goal string to build up dictionary
IDictionary<string, List<int>> dictionary = new Dictionary<string, List<int>>();
for (int nb = 0, position = 0; position < goal.Length; nb++, position += cellLength)
{
string substring = goal.Substring(position, cellLength);
if (!dictionary.ContainsKey(substring))
{
dictionary[substring] = new List<int>();
}
dictionary[substring].Add(nb);
}
if (dictionary.Count <= 0)
{
throw new Exception("No input data ?!");
}
lastNumber = (goal.Length / cellLength) - 1;
starts = new List<Index>();
grid = new Dictionary<int, List<Index>>[rows, cols];
// build up grid and starts
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
string key = gridData[i, j];
if (dictionary.ContainsKey(key))
{
grid[i, j] = new Dictionary<int, List<Index>>();
foreach (int nb in dictionary[key])
{
grid[i, j].Add(nb, null);
if (nb == 0)
{
starts.Add(new Index(i, j));
}
}
}
}
}
}
private void FindSolution(int i, int j, int nb)
{
if (nb == lastNumber)
{
solutions++;
}
else
{
// build neighbors when needed, and memorize after builded.
if (grid[i, j][nb] == null)
{
FindNeighbors(i, j, nb);
}
foreach (Index index in grid[i, j][nb])
{
FindSolution(index.i, index.j, nb + 1);
}
}
}
private void FindNeighbors(int i, int j, int nb)
{
int nextNb = nb + 1;
List<Index> neighbors = new List<Index>();
AddNeighbor(i - 1, j - 1, nextNb, neighbors);
AddNeighbor(i - 1, j , nextNb, neighbors);
AddNeighbor(i - 1, j + 1, nextNb, neighbors);
AddNeighbor(i , j - 1, nextNb, neighbors);
AddNeighbor(i , j + 1, nextNb, neighbors);
AddNeighbor(i + 1, j - 1, nextNb, neighbors);
AddNeighbor(i + 1, j , nextNb, neighbors);
AddNeighbor(i + 1, j + 1, nextNb, neighbors);
grid[i, j][nb] = neighbors;
}
private void AddNeighbor(int i, int j, int nb, List<Index> list)
{
if (i >= 0 && i < rows &&
j >= 0 && j < cols &&
grid[i, j] != null &&
grid[i, j].ContainsKey(nb))
{
list.Add(new Index(i, j));
}
}
}
}
This entry was posted
on Friday, March 28th, 2008 at 1:45 pm and is filed under C#.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.