leetcode764 Largest Plus Sign

思路：

首先使用dp计算出在每个位置(i, j)上下左右最多有多少个连续的1，得到up[i][j], down[i][j], left[i][j], right[i][j]。然后计算这四个值中的最小值，所有最小值中的最大值就是答案。

实现：

 class Solution

 {

 public:

     int orderOfLargestPlusSign(int N, vector<vector<int>>& mines)

     {

         vector<vector<int>> left(N, vector<int>(N, )), right(N, vector<int>(N, ));

         vector<vector<int>> up(N, vector<int>(N, )), down(N, vector<int>(N, ));

         vector<vector<int>> a(N, vector<int>(N, ));

         for (int i = ; i < mines.size(); i++)

             a[mines[i][]][mines[i][]] = ;

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

         {

             left[i][] = (a[i][] ==  ?  : );

             right[i][N - ] = (a[i][N - ] ==  ?  : );

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

             {

                 left[i][j] = a[i][j] ==  ?  : left[i][j - ] + ;

                 right[i][N -  - j] = a[i][N -  - j] ==  ?  : right[i][N - j] + ;

             }

         }

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

         {

             up[][j] = (a[][j] ==  ?  : );

             down[N - ][j] = (a[N - ][j] ==  ?  : );

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

             {

                 up[i][j] = a[i][j] ==  ?  : up[i - ][j] + ;

                 down[N -  - i][j] = a[N -  - i][j] ==  ?  : down[N - i][j] + ;

             }

         }

         int maxn = ;

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

         {

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

             {

                 int tmp = min(min(min(up[i][j], down[i][j]), left[i][j]), right[i][j]);

                 maxn = max(maxn, tmp);

             }

         }

         return maxn;

     }

 };