首先最简单的思路就是深度优先遍历：
class Solution {
public:
const int CARRY = 51;
int maxAreaOfIsland(vector<vector<int> >& grid) {
map<int, bool> earth;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
earth.insert(pair<int, bool>(i*CARRY+j, false));
}
}
}
int theMax = 0;
for (auto one : earth) {
if (!one.second) {
int area = travel(one.first, earth);
theMax = std::max(theMax, area);
}
}
return theMax;
}
int travel(int pos, map<int, bool> &earth) {
int area = 0;
if (earth.find(pos) != earth.end()) {
if (earth[pos] == false) {
earth[pos] = true;
int x = pos / CARRY, y = pos % CARRY;
area = 1
+ travel((x-1)*CARRY + y, earth)
+ travel((x+1)*CARRY + y, earth)
+ travel(x*CARRY + y - 1, earth)
+ travel(x*CARRY + y + 1, earth);
}
}
return area;
}
};
结果：
Runtime:52 ms, faster than 12.74% of C++ online submissions for Max Area of Island.
Memory Usage:20.5 MB, less than 7.80% of C++ online submissions for Max Area of Island.
方案二：
一行一行遍历，每一次查看有没有左边或者上边相邻的点，有则连在一起构成新的岛屿。
class Solution {
public:
const int CARRY = 51;
map<int, shared_ptr<set<int> > > earthMap;
int maxAreaOfIsland(vector<vector<int> >& grid) {
int theMax = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
int area = enlargeIsland(posInt(i,j));
theMax = std::max(theMax, area);
}
}
}
return theMax;
}
int enlargeIsland(int pos) {
int i = pos % CARRY, j = pos / CARRY;
list<shared_ptr<set<int> > > nearByEarths;
if (earthMap.find(posInt(i - 1, j)) != earthMap.end()) {
nearByEarths.push_back(earthMap[posInt(i - 1, j)]);
earthMap.erase(posInt(i - 1, j));
}
if (earthMap.find(posInt(i, j - 1)) != earthMap.end()) {
nearByEarths.push_back(earthMap[posInt(i, j - 1)]);
earthMap.erase(posInt(i, j - 1));
}
shared_ptr<set<int> > joinedEarth = make_shared<set<int> >();
earthMap.insert(pair<int, shared_ptr<set<int> > >(posInt(i, j), joinedEarth));
joinedEarth->insert(posInt(i, j));
int joinedArea = 1;
for (auto earthIter : nearByEarths) {
for (int earthPos : *earthIter) {
earthMap[earthPos] = joinedEarth;
if (joinedEarth->find(earthPos) == joinedEarth->end()) {
joinedArea++;
joinedEarth->insert(earthPos);
}
}
}
return joinedArea;
}
int inline posInt(int x, int y) {
return x + CARRY * y;
}
};
本来还想着方案二回快些，执行结果发现还超时了……
2-1、还得思考下为什么方案二比一慢
2-2、有没有别的方案，因为目前方案一在leetcode的排名看来，还不是最快的算法。
方案三：
看了下排名靠前的答案，跟我方案一的思路差不多呀，只不过我的办法啰嗦了点？
因此作以下改进：
class Solution {
public:
int maxAreaOfIsland(vector<vector<int> >& grid) {
int theMax = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
int area = travel(i, j, grid);
theMax = std::max(theMax, area);
}
}
}
return theMax;
}
int travel(int x, int y, vector<vector<int> > &grid) {
int area = 0;
if (grid[x][y] == 1) {
grid[x][y] = 0;
area = 1
+ (x - 1 >= 0 ? travel(x-1, y, grid) : 0)
+ (x + 1 < grid.size() ? travel(x+1, y, grid) : 0)
+ (y - 1 >= 0 ? travel(x, y - 1, grid) : 0)
+ (y + 1 < grid[0].size() ? travel(x, y + 1, grid) : 0);
}
return area;
}
};
成绩：
Runtime:20 ms, faster than 98.60% of C++ online submissions for Max Area of Island.
Memory Usage:14.7 MB, less than 52.48% of C++ online submissions for Max Area of Island.
