package com.tolchev.algo.matrix

class DetectCycles2DFast {
    fun containsCycle(grid: Array<CharArray>): Boolean {

        val possibleSteps = arrayOf (-1 to 0, 1 to 0, 0 to-1, 0 to 1)

        var visited = Array(grid.size){ BooleanArray(grid[0].size){false} }

        val maxRow = grid.size
        val maxCol = grid[0].size

        fun hasCycle(from: Pair<Int, Int>, current: Pair<Int, Int>, currentChar : Char, visited : Array<BooleanArray>): Boolean {
            visited[current.first][current.second] = true;

            for (step in possibleSteps) {
                var row = current.first + step.first
                var col = current.second + step.second

                val target = Pair(row, col)

                if (from.first == row && from.second == col) continue

                if (row in 0..<maxRow
                    && col in 0 ..<maxCol
                    && grid[row][col] == currentChar){

                    if (visited[target.first][target.second]) return true

                    if (hasCycle(current, target, currentChar, visited)) return true
                }
            }

            return false
        }

        for (row in grid.indices)
            for(col in grid[0].indices)
            {
                val point = Pair(row, col)
                if(!visited[row][col]){
                    if (hasCycle(point, point, grid[row][col], visited)) return true
                }
            }

        return false
    }
}