# DFS, BFS, binary search and brute force interation.

• I will show four algorithms and corresponding complexity;

• DFS : roughly 4k * n^2, k means the factor of num of '1' cell versus image size; This algorithm performs well while k << log2(N) / N;
• BFS : same as DFS
• Binary Search: search for the bounding row and col which has '1', which performs well while many cells are filled with '1'
• brute force: just iterate all of the cells and calc the min_x, min_y, max_x, max_y;

DFS

``````class Solution {
vector<pair<int, int>> dirs;
public:
Solution(){
dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
}
int minArea(vector<vector<char>>& image, int x, int y) {
image[x][y] = '2';
fill_to_boundary(image, x, y);

int xdim, ydim;
xdim = ydim = 0;

for(int i = 0; i <= image.size() - 1; ++i){
if (image[i][y] == '2'){
++xdim;
}
}
for(int i = 0; i <= image[0].size() - 1; ++i){
if (image[x][i] == '2'){
++ydim;
}
}
return  xdim * ydim;
}

void fill_to_boundary(vector<vector<char>>& image, int x, int y){
for(int i = 0; i < dirs.size(); ++i){
int row = x + dirs[i].first;
int col = y + dirs[i].second;
if (row >=0 && row <= image.size() - 1 && col >= 0 && col <= image[0].size() - 1 && need_change(image, row, col)){
image[row][col] = '2';
fill_to_boundary(image, row, col);
}
}
}
bool need_change(vector<vector<char>>& image, int x, int y){
if (image[x][y] == '1') return true;
if (image[x][y] == '2') return false;
int count = 0;
for(int i = 0; i < dirs.size(); ++i){
int row = x + dirs[i].first;
int col = y + dirs[i].second;
if (row >=0 && row <= image.size() - 1 && col >= 0 && col <= image[0].size() - 1 && (image[row][col] == '1' || image[row][col] == '2')){
++ count;
}
}
if (count > 1){
return true;
} else {
return false;
}
}
};
``````

Brute Force

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
int x_min = INT_MAX, y_min = INT_MAX, x_max = INT_MIN, y_max = INT_MIN;
for(int i = 0; i < image.size(); ++i){
for(int j = 0; j < image[0].size(); ++j){
if (image[i][j] == '1'){
x_min = min(x_min, i);
y_min = min(y_min, j);
x_max = max(x_max, i);
y_max = max(y_max, j);
}
}
}
return (x_max - x_min + 1) * (y_max - y_min + 1);
}
};
``````

Binary Search:

Maybe you can refer to https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.