Find closest BFS - Oct. 12, 2020 - 11:00 AM

FindClosestBFS.cs

/* 
[[0,0,0],
 [0,1,0],
 [0,0,0]] => input
 
 output => [[0,0,0],
            [0,1,0],
            [0,0,0]]
            
[[0,0,0],
 [0,1,0],
 [1,1,1]]

[[0,0,0],
 [0,1,0],
 [1,2,1]]
 
 add all 0 position - BFS
 turn 0 -> 1
 search those 1's position -> BFS -> 
 space -> extra -> save as 1 -> negative -> 0, distance -1 
 
 O(n * m)  - all nodes will be visited
 */
/// empty, 0 rows - 0 cols
/// 
//[[0,0,0],
//            [0,1,0],
//            [0,0,0]]
// 8 positions except into Queue
// (0,0) -> (0, 1) -> 1 -> -1
// -1 -> 0 -> terminate
//[[0,0,0],
// [0,1,0],
// [1,1,1]]
// 5 0's into 
//[[0, 1, 1],
//  [1,1,1]
//  [1,1,1]]

using System;
using System.Collections.Generic;

// To execute C#, please define "static void Main" on a class
// named Solution.

class Solution
{
    static void Main(string[] args)
    {
        // first test case - dimension, jagged array 
        int row = 3;
        var matrix = new int[row][];
        for(int i =0; i < row; i++)
            matrix[i] = new int[3];
        
        //matrix[1][1] = 1; 
        for(int i = 0; i < row;i++)
            for(int j = 0; j < row; j++ )
                matrix[i][j] = 1;
        
        matrix[0][0] = 0; 
        
        var result = findCloseDistance(matrix); 
        for(int i =0; i < row; i++)
            for(int j =0; j < row; j++)
                Console.WriteLine(result[i][j]);
    }
    
    public static int[][] findCloseDistance(int[][] matrix)
{
    if(matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
        return new int[0][];
    
    // BFS
    var rows = matrix.Length;
    var columns = matrix[0].Length; 
    var queue = new Queue<int[]>();
    
    var closed = new int[rows][];
    for(int i = 0; i < rows; i++)
        closed[i] =  new int[columns]; // default 0
    
     for(int row = 0; row < rows; row++)
    {
        for(int col = 0; col < columns; col++)
        {
            closed[row][col] = matrix[row][col];
        }
     }
    
    for(int row = 0; row < rows; row++)
    {
        for(int col = 0; col < columns; col++)
        {
            if(matrix[row][col] == 0)
            {
                var numbers = new int[]{row, col};
                queue.Enqueue(numbers);
            }
        }
    }
    
    // apply BFS
    int level = 1; 
    while(queue.Count > 0)
    {
        var levelCount = queue.Count; 
        for(int i = 0; i < levelCount; i++)
        {
            var node = queue.Dequeue(); 
            var row = node[0];
            var col = node[1]; 
            
            // four neighbors if there is 1
            // clockwise, top,right, down, left
            var directionRow = new int[]{-1, 0, 1, 0};
            var directionCol = new int[]{0, 1, 0, -1};
            
            for(int k = 0; k < 4; k++)
            {
                var nRow = row + directionRow[k];
                var nCol = col + directionCol[k];
                
                if(nRow >=0 && nRow < rows && nCol >=0 && nCol < columns && closed[nRow][nCol] == 1)
                {
                    closed[nRow][nCol] = -1 * level;
                    queue.Enqueue(new int[]{nRow, nCol});
                }
            }
        }
        
        
        level++;
    }
    
    // turn negative to positive
     for(int row = 0; row < rows; row++)
    {
        for(int col = 0; col < columns; col++)
        {
            closed[row][col] = Math.Abs(closed[row][col]);  
        }
     }
    
    return closed; 
 }
}