LC 562. Longest Line of Consecutive One in Matrix

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

Input:

[[0,1,1,0],

 [0,1,1,0],

 [0,0,0,1]]

Output: 3

Hint: The number of elements in the given matrix will not exceed 10,000.

Median的题就是简单一点。

1. DFS没有问题。

2. 怎么保存已经遍历过的点，因为每一个点可能有4个方向，所以可以开一个map记录每一个点的四个方向有没有被经过。

我的思路，Runtime有点慢。

Runtime: 88 ms, faster than 13.53% of C++ online submissions for Longest Line of Consecutive One in Matrix.

#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)

#define REP(i, n) FOR(i, 0, n)

#include <vector>

#include <unordered_map>

using namespace std;

class Solution {

private:

  unordered_map<int, vector<bool>> mp;

  int dirs[][] = {{,},{,},{,},{,-}};

  int n,m;

public:

    int longestLine(vector<vector<int>>& M) {

      n = M.size();

      m = M[].size();

      int ret;

      REP(i,n){

        REP(j,m){

          mp[i*m+j] = {false,false,false,false};

        }

      }

      REP(i,n){

        REP(j,m){

          if(M[i][j] == ){

            dfs(M, i, j, ret);

          }

        }

      }

      return ret;

    }

  bool valid(int x, int y){

    return x < n && x >=  && y < m && y >= ;

  }

  void dfs(vector<vector<int>>& M, int x, int y, int& ret){

    if(x <  || y <  || x >= n || y >= m) return ;

    if(M[x][y] == ) return ;

    REP(i, ){

      if(mp[x*m+y][i]) continue;

      mp[x*m+y][i] = true;

      int tmpx = x, tmpy = y, dx = dirs[i][], dy = dirs[i][];

      int cnt = ;

      while(valid(tmpx+dx,tmpy+dy) && M[tmpx+dx][tmpy+dy] == ){

        tmpx += dx;tmpy += dy;

        mp[tmpx*m+tmpy][i] = true;

        cnt++;

      }

      tmpx = x, tmpy = y, dx = -dirs[i][], dy = -dirs[i][];

      while(valid(tmpx+dx,tmpy+dy) && M[tmpx+dx][tmpy+dy] == ){

        tmpx += dx; tmpy += dy;

        mp[tmpx*m+tmpy][i] = true;

        cnt++;

      }

      ret = max(ret, cnt);

    }

  }

};

//[[0,1,1,0],

 //[0,1,1,0],

 //[0,0,0,1]]

int main(){

  vector<vector<int>> M {{,,,},{,,,},{,,,}};

  return ;

}

另一个思路使用dp，dp的精髓在于前后的状态无关，有点类似马尔可夫链。

从矩阵第一行向下遍历，每一次保存的就是当前点四个方向的最大长度，如果点是1，该方向加1。也是很好的思路。

class Solution {

public:

    int longestLine(vector<vector<int>>& M)

    {

        int r=M.size();

        if(r==) return ;

        int c=M[].size();

        vector<vector<vector<int> > > dp(r,vector<vector<int>> (c,vector<int>(,) ) );

        int res=;

        for(int i=;i<r;i++)

            for(int j=;j<c;j++)

            {

                if(M[i][j])

                {

                    dp[i][j][]=j?dp[i][j-][]+:;

                    dp[i][j][]=i?dp[i-][j][]+:;

                    dp[i][j][]=i&&j?dp[i-][j-][]+:;

                    dp[i][j][]=i>&&j<c-?dp[i-][j+][]+:;

                    for(auto x:dp[i][j])

                        res=max(res,x);

                }

            }

        return res;

    }

};

巴特西

LC 562. Longest Line of Consecutive One in Matrix

最新文章

热门文章