- #1

- 141

- 11

e.g. in the following

Code:

```
A - B - C
\ / / \
D E F G
```

the shortest path to F from A would be A -> B -> C -> F.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- C/++/#
- Thread starter SlurrerOfSpeech
- Start date

- #1

- 141

- 11

e.g. in the following

Code:

```
A - B - C
\ / / \
D E F G
```

the shortest path to F from A would be A -> B -> C -> F.

- #2

- 109

- 35

- #3

Mark44

Mentor

- 35,115

- 6,856

Between it and what? The next node?every node has the same distance between it

- #4

- 141

- 11

Code:

```
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
```

and have to move from the 'M' to the '*' along the '.' characters, where in a single move I can travel over any number of characters '.' in a single direction. The 'X' characters are obstructions.

My code is well-annotated. (The only confusing part may be that I transpose the original matrix so that I can access in the more natural [x,y] index structure instead of [y,x]).

Code:

```
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
// Algorithm explanation:
//
// Suppose we have a grid like
//
// . . X
// . . .
// * X M
//
// Since we can travel along the the dots any distance in a
// single move, a graph of the possible moves is like
//
// (0,0) -------- (1,0)
// / \ |
// / \ |
// (0,2)---(0,1) --- (1,1)
// \ /
// \ /
// \ /
// (2,1)
// /
// /
// (2,2)
//
// where the distance between every node is 1. We're trying to get
// from node (2,2) to node (0,2) in the shortest route. We can use
// a BFS to find this route.
class Node
{
// coordinates
public int X { get; set; }
public int Y { get; set; }
// parent node
public Node Parent { get; set; } = null;
// distance from root node
public int Distance { get; set; } = Int32.MaxValue; // "infinity"
// nodes connected to this one
public List<Node> Neighbors { get; set; } = new List<Node>();
}
class ForbiddenForest
{
private Node[,] _tree;
private Node _start;
private Node _end;
public ForbiddenForest(char[,] mat)
{
BuildTree(mat);
}
// helper method for traversing a 2-D array
private static IEnumerable<T> MultiElements<T>(T[,] source)
{
for(int i = 0, n = source.GetLength(0); i < n; ++i)
for(int j = 0, m = source.GetLength(1); j < m; ++j)
yield return source[i, j];
}
private void BuildTree(char[,] mat)
{
int m = mat.GetLength(0),
n = mat.GetLength(1);
_tree = new Node[m, n];
// Add all the nodes to the tree with their x-y positions.
// Set the start and end nodes when we come across them.
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
switch(mat[i, j])
{
case '.':
_tree[i, j] = new Node() { X = i, Y = j };
break;
case 'M':
_tree[i, j] = new Node() { X = i, Y = j };
_start = _tree[i, j];
break;
case '*':
_tree[i, j] = new Node() { X = i, Y = j };
_end = _tree[i, j];
break;
}
}
}
var nodes = MultiElements(_tree).Where(z => z != null);
// Now add the neighbors. To do this, start at the node's x-y
// position on the graph and move as far possible up, right,
// down and left, collecting the nodes as we move along.
foreach(var node in nodes)
{
int x = node.X, y = node.Y;
// up:
while (--y >= 0 && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
// right:
y = node.Y;
while (++x < m && _tree[y, y] != null)
node.Neighbors.Add(_tree[x, y]);
// down:
x = node.X;
while (++y < n && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
// left:
y = node.Y;
while (--x >= 0 && _tree[x, y] != null)
node.Neighbors.Add(_tree[x, y]);
}
// Now fill in the Distance and Parent values by using the BFS
// algorithm on https://en.wikipedia.org/wiki/Breadth-first_search
var Q = new Queue<Node>();
_start.Distance = 0;
Q.Enqueue(_start);
while(Q.Count > 0)
{
var current = Q.Dequeue();
foreach(var neighbor in current.Neighbors)
{
if(neighbor.Distance == Int32.MaxValue)
{
neighbor.Distance = current.Distance + 1;
neighbor.Parent = current;
Q.Enqueue(neighbor);
}
}
}
}
public int OptimalMoveNumbers { get { return _end.Distance; } }
}
class Solution
{
static void Main(String[] args)
{
int T = Int32.Parse(Console.ReadLine());
for(int t = 0; t < T; ++t)
{
int[] line = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int N = line[0], M = line[1];
char[,] matrix = new char[M,N];
for(int i = 0; i < N; ++i)
{
char[] row = Console.ReadLine().Where(c => c != ' ').ToArray();
for(int j = 0; j < M; ++j)
matrix[j,i] = row[j];
}
int K = Int32.Parse(Console.ReadLine());
var ff = new ForbiddenForest(matrix);
Console.WriteLine(K == ff.OptimalMoveNumbers() ? "Impressed" : "Oops!");
}
}
}
```

- #5

Mark44

Mentor

- 35,115

- 6,856

Then my advice is to try smaller examples, such as your 3 x 3 example you show in comments, or 4 x 4 or 5 x 5.Can someone help me figure out where I'm going wrong in my solution? It's failing some of the test cases and they're too big for me to possibly step through.

Debatable. Main() has no comments. Comments in Main() would help the reader understand what it is doing, especially in.the last two lines.My code is well-annotated.

BuildTree could use some comments in the switch statement.

Also, in BuildTree, you have this comment:

There are eight possible directions from each node, not just the four that you show in the comment.// Now add the neighbors. To do this, start at the node's x-y

// position on the graph and move as far possible up, right,

// down and left,

IMO, the transpose is not really necessary. The matrix you show as your map example threw me off for a time, because the X in the upper right corner would be in row 0, column 2. IOW, the "natural" indexes of a 2-D matrix are in y, x form. As long as everyone understands your system, it's fine, though.SlurrerOfSpeech said:(The only confusing part may be that I transpose the original matrix so that I can access in the more natural [x,y] index structure instead of [y,x]).

Unclear. Better: The distance between each node and an adjacent node is 1.where the distance between every node is 1

Share: