Waterfall Streams

• Time : O(w * h)
• Space : O(w)

c++

#include <vector>

using namespace std;

vector<double> waterfallStreams(vector<vector<double>> array, int source) {
    int n = array.size(), m = array[0].size();
    vector<double> dp(m, 0.0);
    dp[source] = 100.0;
    for(int i = 0; i < n; i++) {
        vector<double> nxt(m, 0.0);
        double water = 0.0;
        for(int j = 0; j < m; j++) {
            if(i and array[i-1][j] == 1.0)
                water = 0.0;
            water += dp[j] / 2;
            if(array[i][j] == 0.0) {
                nxt[j] += water;
                water = 0.0;
            }
        }
        water = 0.0;
        for(int j = m - 1; j >= 0; j--) {
            if(i and array[i-1][j] == 1.0)
                water = 0.0;
            water += dp[j] / 2;
            if(array[i][j] == 0.0) {
                nxt[j] += water;
                water = 0.0;
            }
        }
        swap(nxt, dp);
    }

    return dp;
}