# Matrix
###### tags: `Study_aboard`

## Spiral Matrix

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
        int border_up=-1, border_down=matrix.size(), border_left=-1, border_right=matrix[0].size();
        vector <int> res;
        char direction = 'r';
        int cur_x=0, cur_y=0;
        
        while(res.size()<(matrix.size()*matrix[0].size()) ){
            
            res.push_back(matrix[cur_x][cur_y]);
            
            
            if(direction == 'r'){
                
                if(cur_y+1 < border_right){   
                    cur_y = cur_y+1;
                }
                else{
                    direction = 'd';
                    border_up++;
                    cur_x = cur_x+1;
                }
            } 
            
            else if(direction == 'd'){
                
                if(cur_x+1 < border_down){   
                    cur_x = cur_x+1;
                }
                else{
                    direction = 'l';
                    border_right--;
                    cur_y = cur_y-1;
                }
            }
            
            else if(direction == 'l'){
                
                if(cur_y-1 > border_left){   
                    cur_y = cur_y-1;
                }
                
                else{
                    direction = 'u';
                    border_down--;
                    cur_x --;
                }
            }
            
            else if(direction == 'u'){
                
                if(cur_x-1 > border_up){   
                    cur_x = cur_x-1;
                }
                else{
                    direction = 'r';
                    border_left++;
                    cur_y = cur_y+1;
                }
            }
            
        }
        
        return res;
        
    }
};

## Search a 2d Matrix

easy
sorted array -> use binary search
see https://hackmd.io/@chentzj/SkNIsGDpu binary search

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
            return false;
        
        int left = 0, right = matrix.size();
        
        // row use binary search II - search the first number that is greater or equal to the target
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] < target) left = mid + 1;
            else right = mid;
        }
        // right-1 will be the row we want
        int tmp = (right > 0) ? (right - 1) : right;
        
        left = 0;
        right = matrix[tmp].size();
        
        // binary search I
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[tmp][mid] == target) return true;
            if (matrix[tmp][mid] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

## Search a 2d Matrix II

要能夠search，需要先找出一致性。
觀察左下角與右上角，發現其邊有一致性，以左下角為例，其上方都是小於它的數字，而右方都是大於它的數字

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
            return false;
        if (target < matrix[0][0] || target > matrix.back().back()) 
            return false;
        
        int x = matrix.size() - 1, y = 0;
        // x is row, y is col
        
        while (true) {
            if (matrix[x][y] > target) 
                --x;
            else if (matrix[x][y] < target) 
                ++y;
            else return true;
            
            if (x < 0 || y >= matrix[0].size()) 
                break;
        }
        return false;
    }
};

## Maximum Number of Points with Cost

Initial : divide and conquer
problem: TLE time complexity O(m * n * n)
solution: find same computation to reduce complexity

original version

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        
        
        long long int m = points.size(), n=points[0].size();
        vector<vector<long long int>> dp(m, vector<long long int>(n, 0));
        
        for(int i=0;i<n;i++){
            dp[0][i] = points[0][i];
        }
        
        // i is row, j is col
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                
                long long int Max = INT_MIN;
                
                for(int k=0;k<n;k++){
                    Max = max(Max,points[i][j]+dp[i-1][k]-abs(j-k));
                }
                dp[i][j] = Max;
            }
        }
        
        long long int res=0;
        
        for(int i=0;i<n;i++){
            res = max(dp[m-1][i], res);
        }
        return res;
    }
};

Initial:

Sol:若將abs(j-k)區分為 j-k (j>k) & k-j (k>j)，==則j與k之間並沒有關係==，可以==獨立拆出==而不須在j loop中執行k。


class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        vector<vector<long long>> dp(points.size(), vector<long long>(points[0].size(), -1));
        
        for (int i = 0; i < points[0].size(); ++i) {
            dp[0][i] = points[0][i];
        }
        
        for (int i = 1; i < points.size(); ++i) {
            vector<long long> left_dp(points[i].size(), -1);
            vector<long long> right_dp(points[i].size(), -1);
            // left_dp : the maximum value of dp[i-1][k'] from 0~k
            // right_dp : the maximum value of dp[i-1][k'] from k~size()-1
            
            left_dp[0] = dp[i - 1][0];
            for (int k = 1; k < points[i].size(); ++k) {
                left_dp[k] = max(left_dp[k - 1], dp[i - 1][k] + k);
            }
            
            right_dp.back() = dp[i - 1].back() - points[i].size() + 1;
            for (int k = points[i].size() - 2; k >= 0; --k) {
                right_dp[k] = max(right_dp[k + 1], dp[i - 1][k] - k);
            }
            
            for (int j = 0; j < points[i].size(); ++j) {
                dp[i][j] = max(left_dp[j] - j, right_dp[j] + j) + points[i][j];
            }
        }
        
        long long max_ans = -1;
        for (const auto v : dp.back()) {
            max_ans = max(max_ans, v);
        }
        
        return max_ans;
    }
};

## Longest Increasing Path in a Matrix


1. DFS

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        int res = 0;
        
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                
                res = max(res,dfs(i,j,dp, matrix)) ;
            }
        }
        return res;
    }
    
    int dfs(int i, int j, vector<vector<int>>& dp,vector<vector<int>>& matrix){
        
        int mx = 1;
        int len = 0;
        int m = matrix.size(), n = matrix[0].size(); 
        
        vector<vector<int>> dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        
        for (auto a : dirs) {
            int x = i + a[0], y = j + a[1];
            
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) 
                continue;
            
            if (dp[x][y]){
                len = 1 + dp[x][y];
            }
            else{
                len = 1 + dfs(x, y,dp, matrix);
            }
            mx = max(mx, len);
        }
        dp[i][j] = mx;
        return mx;
    }
};

## Sparse Matrix ==Facebook, google==
Nothing sepcial

class Solution {
public:
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
        vector< vector<int> > AB;
        AB.clear();
        int rowA = A.size(), columnA = A[0].size();
        int rowB = B.size(), columnB = B[0].size();
        // AB为 rowA * columnB 大小的矩阵
        for (int i = 0; i < rowA; i++){
            vector<int> tmp;
            tmp.clear();
            for (int j = 0; j < columnB; j++){
                // 求出每一项
                int sum = 0;
                for (int k = 0; k < columnA; k++){
                    sum += A[i][k] * B[k][j];
                }
                tmp.push_back(sum);
            }
            AB.push_back(tmp);
        }
        return AB;
    }
};

## Best meeting point ==Hard==
good problem
==Hint simplify the question first!!!==

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> rows, cols;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == 1) {
                    rows.push_back(i);
                    cols.push_back(j);
                }
            }
        }
        return minTotalDistance(rows) + minTotalDistance(cols);
    }
    int minTotalDistance(vector<int> v) {
        int res = 0;
        sort(v.begin(), v.end());
        int i = 0, j = v.size() - 1;
        while (i < j) res += v[j--] - v[i++];
        return res;
    }
};

## Minimum Garden Perimeter to Collect Enough Apples

Perimeter i = Perimeter i-1 + additional items

Additional items:
- 最外面上下左右四點 + 在x軸與y軸上的四點 = $2n*4 + n*4$ = $12*n$
- 4 \* (在x軸到右上方的點n + 右上方到y軸上n) = $2n*(n-1)*4$
- 4 \* (在x軸到右上方的點1~n + 右上方到y軸上1~n) = $n*(n-1)*4$

Sum = $12*n^2$

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        
        long long old_val=0, new_val=0;
        
        for(int i=1; ;i++){
            new_val = old_val + 12 * pow(i,2);
            if(new_val>=neededApples) return i*2*4;
            else old_val = new_val;
        }
        return new_val;
    }
};

## Walls and Gates

Initial: do BFS for each empty room until reach the gate
If we reach a room that we are already done, we can return cur path + room path

Sol: start from empty gates may be faster !!

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        
        queue<pair<int, int>> q;// bfs queue for row and col
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // bfs children
        
        for (int i = 0; i < rooms.size(); ++i) {
            for (int j = 0; j < rooms[i].size(); ++j) {
                if (rooms[i][j] == 0) q.push({i, j});   
            }
        }

        while (!q.empty()) {
            int i = q.front().first, j = q.front().second; 
            q.pop();
            for (int k = 0; k < dirs.size(); ++k) {
                int x = i + dirs[k][0], y = j + dirs[k][1];
                /* child does not exist
                // rooms[x][y] < rooms[i][j] + 1
                // 1. rooms[x][y] = -1
                // 2. rooms[x][y] already walk through by a smaller distance gate
                */
                if (x < 0 || x >= rooms.size() || y < 0 || y >= rooms[0].size() || rooms[x][y] < rooms[i][j] + 1) continue; 

                rooms[x][y] = rooms[i][j] + 1;
                q.push({x, y});
            }
        }
    }
};

## Shortest Distance from all buildings

初始想法:BFS算出每個building的distane map，加總取最小值

dist: temporary distane map
sum: sum of each temporary distance map
bfs: implement by queue
visit: bfs需要記得已走過的位置，因此將做完後的grid--來達成。而下一輪==的val也要--。此處有可能有疑問，可能有上一個building無法走到的empty space而導致仍為0，但下一個building是能夠通過的。但由於題目規定need to reach all buildings，因此此empty space也不能作為路徑。

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int res = INT_MAX, val = 0, m = grid.size(), n = grid[0].size();
        vector<vector<int>> sum = grid;
        vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == 1) {
                    res = INT_MAX;
                    vector<vector<int>> dist = grid;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    while (!q.empty()) {
                        int a = q.front().first, b = q.front().second; q.pop();
                        for (int k = 0; k < dirs.size(); ++k) {
                            int x = a + dirs[k][0], y = b + dirs[k][1];
                            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == val) {
                                --grid[x][y];
                                dist[x][y] = dist[a][b] + 1;
                                sum[x][y] += dist[x][y] - 1;
                                q.push({x, y});
                                res = min(res, sum[x][y]);
                            }
                        }
                    }
                    --val;                    
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};