(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

(0, 1, x, 1, 1)
(1, 1, x, 1, 1)
(1, 0, x, 0, 1)
(1, 1, x, 1, 1)
(1, 0, x, 1, 0)

(0, x, x, 1, 1)
(1, x, x, 1, 1)
(1, x, x, 0, 1)
(1, x, x, 1, 1)
(1, x, x, 1, 0)

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

public class Hungarian {
    public static void main(String[] args) {
        // m1 input values
        int[][] m1 = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 1 },
                { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 0 } };

        // int[][] m1 = { {13,14,0,8},
        // {40,0,12,40},
        // {6,64,0,66},
        // {0,1,90,0}};

        // int[][] m1 = { {0,0,100},
        // {50,100,0},
        // {0,50,50}};

        // m2 max(horizontal,vertical) values, with negative number for
        // horizontal, positive for vertical
        int[][] m2 = new int[m1.length][m1.length];

        // m3 where the line are drawen
        int[][] m3 = new int[m1.length][m1.length];

        // loop on zeroes from the input array, and sotre the max num of zeroes
        // in the m2 array
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (m1[row][col] == 0)
                    m2[row][col] = hvMax(m1, row, col);
            }
        }

        // print m1 array (Given input array)
        System.out.println("Given input array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m1[row][col] + "t");
            }
            System.out.println();
        }

        // print m2 array
        System.out
                .println("nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m2[row][col] + "t");
            }
            System.out.println();
        }

        // Loop on m2 elements, clear neighbours and draw the lines
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (Math.abs(m2[row][col]) > 0) {
                    clearNeighbours(m2, m3, row, col);
                }
            }
        }

        // prinit m3 array (Lines array)
        System.out.println("nLines array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m3[row][col] + "t");
            }
            System.out.println();
        }
    }

    // max of vertical vs horizontal at index row col
    public static int hvMax(int[][] m1, int row, int col) {
        int vertical = 0;
        int horizontal = 0;

        // check horizontal
        for (int i = 0; i < m1.length; i++) {
            if (m1[row][i] == 0)
                horizontal++;
        }

        // check vertical
        for (int i = 0; i < m1.length; i++) {
            if (m1[i][col] == 0)
                vertical++;
        }

        // negative for horizontal, positive for vertical
        return vertical > horizontal ? vertical : horizontal * -1;
    }

    // clear the neighbors of the picked largest value, the sign will let the
    // app decide which direction to clear
    public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) {
        // if vertical
        if (m2[row][col] > 0) {
            for (int i = 0; i < m2.length; i++) {
                if (m2[i][col] > 0)
                    m2[i][col] = 0; // clear neigbor
                m3[i][col] = 1; // draw line
            }
        } else {
            for (int i = 0; i < m2.length; i++) {
                if (m2[row][i] < 0)
                    m2[row][i] = 0; // clear neigbor
                m3[row][i] = 1; // draw line
            }
        }

        m2[row][col] = 0;
        m3[row][col] = 1;
    }
}

Given input array
0   1   0   1   1
1   1   0   1   1
1   0   0   0   1
1   1   0   1   1
1   0   0   1   0

m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)
-2  0   5   0   0
0   0   5   0   0
0   -3  5   -3  0
0   0   5   0   0
0   -3  5   0   -3

Lines array
1   1   1   1   1
0   0   1   0   0
1   1   1   1   1
0   0   1   0   0
1   1   1   1   1

0  0  1

 0  1  1

 1  0  1

-2 -2  0

 2  0  0

 0  2  0

0  1  1

 1  0  1

 0  0  1

0 0 1 1 1
 0 1 0 1 1
 0 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

3 -2  0  0  0
 3  0 -2  0  0
 3  0  0 -2  0
 0  0 -2 -2  0
 0  0  0  0  0

3 -2  0  0  0
 3  0  0  0  0
 3  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

1 1 1 1 1
 1 1 0 1 1
 1 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

0  0  0  0  0
 0  0  2  0  0
 0  0  0  2  0
 0  0  0  0  0
 0  0  0  0  0

0 0 1 1
 0 1 1 1
 1 0 1 1
 1 1 1 0

0 0 1 1 1
 0 1 1 1 1
 1 0 1 1 1
 1 1 1 0 0
 1 1 1 0 0

function [Lines, AllRows, AllCols] = FindMinLines(InMat)

%The following code finds the minimum set of lines (rows and columns)
%required to cover all of the true-valued cells in a matrix. If using for
%the Hungarian problem where 'true-values' are equal to zero, make the
%necessary changes. This code is not complete, since it will be caught in
%an infinite loop in the case of disjoint-tied-sets

%If passing in a matrix where 0s are the cells of interest, uncomment the
%next line
%InMat = InMat == 0;

%Assume square matrix
Count = length(InMat);
Lines = zeros(Count);

%while there are any 'true' values not covered by lines

while any(any(~Lines & InMat))
    %Calculate row-wise and col-wise totals of 'trues' not-already-covered
    HorzCount = repmat(sum(~Lines & InMat, 2), 1, Count).*(~Lines & InMat);
    VertCount = repmat(sum(~Lines & InMat, 1), Count, 1).*(~Lines & InMat);

    %Calculate for each cell the difference between row-wise and col-wise
    %counts. I.e. row-oriented cells will have a negative number, col-oriented
    %cells will have a positive numbers, ties and 'non-trues' will be 0.
    %Non-zero values indicate lines to be drawn where orientation is determined
    %by sign.
    DiffCounts = VertCount - HorzCount;

    %find the row and col indices of the lines
    HorzIdx = any(DiffCounts < 0, 2);
    VertIdx = any(DiffCounts > 0, 1);

    %Set the horizontal and vertical indices of the Lines matrix to true
    Lines(HorzIdx, :) = true;
    Lines(:, VertIdx) = true;
end

%compute index numbers to be returned.
AllRows = [find(HorzIdx); find(DisjTiedRows)];
AllCols = find(VertIdx);

end

horizontal line (row): {"0":0,"2":2,"4":4}
vertical line (column): {"2":2}

Step 5: Matrix
0  1  0  1  1
1  1  0  1  1
1  0  0  0  1
1  1  0  1  1
1  0  0  1  0

Smallest number in uncovered matrix: 1
Step 6: Matrix
x  x  x  x  x
1  1  x  1  1
x  x  x  x  x
1  1  x  1  1
x  x  x  x  x

def draw_lines grid
    #copies the array
    marking_grid = grid.map { |a| a.dup }

    marked_rows = Array.new
    marked_cols = Array.new

    while there_is_zero(marking_grid) do
        marking_grid = grid.map { |a| a.dup }

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

        marked = assignment(grid, marking_grid)
        marked_rows = marked[0]
        marked_cols.concat(marked[1]).uniq!

        marking_grid = grid.map { |a| a.dup }

        marking_grid.length.times do |row|
            if !(marked_rows.include? row) then
                cross_out(marking_grid,row, nil)
            end
        end

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

    end


    lines = Array.new

    marked_cols.each do |index|
        lines.push(["column", index])
    end
    grid.each_index do |index|
        if !(marked_rows.include? index) then
            lines.push(["row", index])
        end
    end
    return lines
end


def there_is_zero grid
    grid.each_with_index do |row|
        row.each_with_index do |value|
            if value == 0 then
                return true
            end
        end
    end
    return false
end

def assignment grid, marking_grid
    marking_grid.each_index do |row_index|
        first_zero = marking_grid[row_index].index(0)
        #if there is no zero go to next row
        if first_zero.nil? then
            next
        else
            cross_out(marking_grid, row_index, first_zero)
            marking_grid[row_index][first_zero] = "*"
        end
    end

    return mark(grid, marking_grid)
end


def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new
    marking_grid.each_with_index do |row, row_index|
        selected_assignment = row.index("*")
        if selected_assignment.nil? then
            marked_rows.push(row_index)
        end
    end

    marked_rows.each do |index|
        grid[index].each_with_index do |cost, col_index|
            if cost == 0 then
                marked_cols.push(col_index)
            end
        end
    end
    marked_cols = marked_cols.uniq

    marked_cols.each do |col_index|
        marking_grid.each_with_index do |row, row_index|
            if row[col_index] == "*" then
                marked_rows.push(row_index)
            end
        end
    end

    return [marked_rows, marked_cols]
end


def cross_out(marking_grid, row, col)
    if col != nil then
        marking_grid.each_index do |i|
            marking_grid[i][col] = "X"
        end
    end
    if row != nil then
        marking_grid[row].map! {|i| "X"}
    end
end

grid = [
    [0,0,1,0],
    [0,0,1,0],
    [0,1,1,1],
    [0,1,1,1],
]

p draw_lines(grid)