Problem Statement -
Given a matrix of size n*m, where each position is representing a city.
Initially all city are represented by zero. ( means they are not traversible ).
On each day one city will randomly become traversible. ( matrix[i][j] = 1 )

Write an algorithm that can detect when there is a path from any city of first column to any city of last column.

My Approach -

• on each day
  • mark that city as traversible.
  • start dfs from all city of first column and check if we can reach last column.

Time Compl - O((mn)^2).
O(mn) for each DFS and in worst case path will be found when each city is marked as traversible.

Is there a better way to solve this problem, tried solving it using union find but could not find more optimal solution. Please help