You have been assigned to work with an undersea explorer who is attempting to

identify and map undersea trenches. The explorer has provided you with several

data sets of sonar readings in this format:

```js

// Example 1

sonar = [

[-5,-5,-5,-5,-5],

[-5,-8,-8,-9,-7],

[-5,-5,-5,-5,-8],

[-5,-5,-5,-5,-5]

]

```

Depending on the scan, the provided matrix may be larger or smaller, but it will

always be rectangular. Your task is to determine if a given data set contains a

trench by comparing each node and their neighbors and determining if there is a

pattern that matches the defined properties of a trench.

Neighbors are considered to be nodes that are directly above, below, or to

the side. **No diagonals**!

A trench has the following three properties:

1. It has a length of **three or more** nodes that are neighbors.

2. Each node in the trench must be **deeper than -5**.

3. Trenches may **not** branch into (any form of) a "T" shape. A node with more than **two neighbors** will result in branching "T" shape.

This problem literally has edge cases! After discussing the matter with the

explorer, you have agreed that potential trenches that otherwise meet the rules

as a trench are valid, even if part of it is on the edge of the data set, and it

can't be fully determined if those nodes follow the rules.

A few examples

```js

// Example 1

sonar_1 = [

[-5,-5,-5,-5,-5],

[-5,-8,-8,-9,-7],

[-5,-5,-5,-5,-8],

[-5,-5,-5,-5,-5]

]

```

**Example 1 has a trench**. The nodes containing -8, -8, -9, -7, -8 meet the rules.

This is an edge case trench, because the nodes containing -7 and -8 are on the

edge of the data set.

```js

// Example 2

sonar_2 = [

[-5,-5,-5,-7,-5],

[-5,-8,-8,-9,-5],

[-5,-5,-5,-7,-5],

[-5,-5,-5,-5,-5]

]

```

**Example 2 does not have a trench**. The node containing -9 has three neighbors with a

depth below -5. This would make a "T" shaped trench, which is not valid.

```js

// Example 3

sonar_3 = [

[-5,-5,-5,-5,-5],

[-5,-5,-5,-5,-5],

[-5,-9,-9,-5,-5],

[-5,-5,-5,-5,-5]

]

```

**Example 3 does not have a trench**. There are two nodes that are next to one

another and are deeper than -5, but a trench must have at least 3 total nodes to

be a trench.

CODE IN JAVASCRIPT!

function findNeighbors(node, matrix) {

// Only consider N, S, E, W nodes

const neighbors = [] // new array for neighbors

const [row, col] = node // destructure node to get row and col([row, col])

newNode = [

[-1, 0], // North

[1, 0], // South

[0, -1], // East

[0, 1], // West

]

const currentNode = matrix[row][col] // get value for current Node

newNode.forEach(element => {

const [newRow, newCol] = element

const neighRow = row + newRow // add new nodes value for row

const neighCol = col + newCol // add new nodes value for col

// We check new nodes does NOT go out of bounds

if (((neighRow >= 0 && neighRow < matrix.length) && (neighCol >= 0 && neighCol < matrix[row].length))) {

const neighborNode = matrix[neighRow][neighCol]

if (neighborNode < -5) {

neighbors.push([neighRow, neighCol])

}

}

});

return neighbors

}

function trenchTraversal(node, matrix, visited) {

// Don't bother traversing if it is to shallow

// Traverse the potential trench to count it's length

const [row, col] = node // destructure node to get row and col([row, col])

let result = []

const stack = [node]

visited.add([row, col].toString())

while (stack.length) {

let current = stack.pop()

result.push(current)

// console.log(result)

const [currentRow, currentCol] = current

const currentNode = matrix[currentRow][currentCol]

// trench property, if each current node in the trench MUST be >= -5

if (currentNode >= -5) {

return false // returns false if the start is too shallow

}

let neighbors = findNeighbors(current, matrix)

neighbors.forEach(neighbor => {

const neighborStr = ([neighbor[0], neighbor[1]].toString())

if (!visited.has(neighborStr)) {

visited.add(neighborStr)

stack.push(neighbor)

}

// traverses a trench with a "T" that returns false

if (!visited.has(neighbor[0] - 1 && neighbor[1] - 1)) {

// console.log(visited)

return false

}

});

// trench property (edge case)

if (result.length >= 3) { // has length of 3 or more nodes that are neighbors

return true

}

}

return false

}

function identifyTrench(trenchMatrix) {

// Start at 0,0 and attempt to traverse any unvisited nodes

// let visited = new Set()

// let start = trenchMatrix[0][0]

// if (trenchTraversal(start, trenchMatrix, visited)) {

// return true

// }

// return false

}