1.题目描述:
给定一个二维数组，只由0和1组成，求连续1的最大数目（连续的意思是：上下左右）
输入：
grid
:
0 1 0 0
0 0 1 1
0 0 0 1
0 1 1 1
输出：
ans
:
6
2.dfs解法
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std
;
class Solution
{
public:
int computate(vector
<vector
<int>>& grid
)
{
int ans
= 0;
int row
= grid
.size();
int col
= grid
[0].size();
for(int i
=0;i
<row
;i
++)
for (int j
= 0; j
< col
; j
++)
if (grid
[i
][j
] == 1)
{
int tmp
= dfs(grid
, i
, j
,row
, col
);
ans
= max(ans
, tmp
);
}
return ans
;
}
int dfs(vector
<vector
<int>>& grid
, int x
, int y
, int row
, int col
)
{
int dir
[5] = { -1,0,1,0,-1 };
int res
= 1;
grid
[x
][y
] = 0;
for (int i
= 0; i
< 4; i
++)
{
int a
= x
+ dir
[i
];
int b
= y
+ dir
[i
+ 1];
if (a
>= 0 && a
< row
&& b
>= 0 && b
< col
&&grid
[a
][b
] == 1)
res
+= dfs(grid
, a
, b
, row
, col
);
}
return res
;
}
};
int main()
{
vector
<vector
<int>> num
= { {0,1,0,0},{0,0,1,1},{0,0,0,1},{0,1,1,1} };
Solution s
;
int ans
= s
.computate(num
);
cout
<< ans
<< endl
;
system("pause");
return 0;
}
3.bfs解法
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std
;
class Solution
{
public:
using pii
= pair
<int, int>;
int dir
[5] = { -1,0,1,0,-1 };
int ans
= 0, res
= 0;
int computate(vector
<vector
<int>>& grid
)
{
if (grid
.empty() || grid
[0].empty()) return res
;
queue
<pii
> p
;
int row
= grid
.size();
int col
= grid
[0].size();
for (int i
= 0; i
< row
; i
++)
for (int j
= 0; j
< col
; j
++)
if (grid
[i
][j
] == 1)
{
res
=1;
p
.push({ i
,j
});
grid
[i
][j
] = 0;
while (!p
.empty())
{
auto node
= p
.front();
p
.pop();
for (int i
= 0; i
< 4; i
++)
{
int a
= node
.first
+ dir
[i
];
int b
= node
.second
+ dir
[i
+ 1];
if (a
>= 0 && a
< row
&&b
>= 0 && b
< col
&&grid
[a
][b
] == 1)
{
res
++;
grid
[a
][b
] = 0;
p
.push({ a
,b
});
}
}
}
ans
= max(res
, ans
);
}
return ans
;
}
};
int main()
{
vector
<vector
<int>> num
= { {0,1,0,0},{0,0,1,1},{0,0,0,1},{0,1,1,1} };
Solution s
;
int ans
= s
.computate(num
);
cout
<< ans
<< endl
;
system("pause");
return 0;
}
4.bfs和dfs优缺点
图片不知道哪找的，说的大概都对，有一点，dfs的缺点1.标记了以后还要取消，这条持怀疑态度，取消了那叫回溯。dfs和回溯还是有区别 。
