Given a (0,1) grid and coordinates (x,y) find the circumference (perimeter) of the enclosing island of 1's


  • 0
    A

    E.g

    01110
    00110
    11001
    01010
    
    (2,3) : circumference = 10
    (3, 5) or (4,4) : circumference = 4
    (4, 2): circumference = 8
    

  • 0

    Could you clarify the coordinate system used and what exactly is meant by circumference and island?

    Suppose that coordinates start at top-left and 1-based. Suppose an island is defined as a group of 1s horizontally or vertically (but not diagonally) adjacent. If this is the case, I can understand the (3, 5) and (4, 4) cases, but others? (4, 1) seems more like 8, and (2, 3) seems more like 10.


  • 0
    A

    @SergeyTachenov You are correct in understanding the coordinate system and the values. I have edited the post with the correct values! (posted in a hurry and hence the mistakes in values)


  • 0

    All right, so here is how I'd approach it. Looking at these islands, the first thing that comes to mind is BFS. Maybe DFS is an option too, but BFS is easier to visualize, and therefore would probably lead to more readable code, at least for those familiar with BFS. On the other hand, DFS may be easier to implement recursively, only we risk stack overflow for really large matrices because recursion may go too deep. So I'd stick with BFS.

    Using BFS, we can easily find the island, but what about circumference? First thing that comes to mind here is that we could probably count the number of adjacent zeroes, assuming that everything outside the matrix is filled with zeroes too. But we better be careful here lest we run into edge cases, so let's look at the possibilities.

    ...0000...
    ...1111...
    ...1111...
    

    In this case it's pretty clear that the number of adjacent zeroes will do the trick.

    ...0000...
    ...0111...
    ...0111...
    

    The corner case (literally). But it looks like it's still fine: ignoring diagonally adjacent zero, we get exactly what we need.

    ...0001...
    ...0001...
    ...1111...
    

    Another corner case. Now, here things go wrong. The circumference of this part is 5, and we have only four adjacent zeroes. Which means we have to count the corner zero twice. Or we can count unique adjacent pairs 1-0, then it will be counted twice automatically because one zero is adjacent to two 1s.

    ...0000...
    ...0111...
    ...0000...
    

    Here, either approach works.

    ...1111...
    ...1000...
    ...1111...
    

    And here, we again have to count unique pairs. Looks like it is the correct approach after all.

    So, we do BFS, and when we stumble into a zero or the matrix border, we add the pair of coordinates to a set. Then we return the set size.

    struct BorderPiece {
    	const int i1, j1, i2, j2;
    
    	BorderPiece(int i1, int j1, int i2, int j2) :
    		i1(i1), j1(j1), i2(i2), j2(j2)
    	{}
    
    	bool operator==(const BorderPiece &that) const {
    		return i1 == that.i1 && j1 == that.j1
    			&& i2 == that.i2 && j2 == that.j2;
    	}
    };
    
    namespace std {
    	template<>
    	struct hash<BorderPiece> {
    		size_t operator()(const BorderPiece &p) const {
    			return (((p.i1 * 17) + p.j1) * 17 + p.i2) * 17 + p.j2;
    		}
    	};
    }
    
    int circumference(const vector<vector<bool>> &matrix, size_t i, size_t j) {
    	--i; --j; // convert to 0-based
    	const int m = matrix.size(), n = matrix[0].size();
    	auto get = [&matrix, &m, &n](ptrdiff_t i, ptrdiff_t j) {
    		return i >= 0 && i < m && j >= 0 && j < n ? matrix[i][j] : false;
    	};
    	using Coords = pair<size_t, size_t>;
    	unordered_set<BorderPiece> border;
    	vector<vector<bool>> visited(m, vector<bool>(n));
    	visited[i][j] = true;
    	queue<Coords> q;
    	q.push(Coords(i, j));
    	using Step = pair<ptrdiff_t, ptrdiff_t>;
    	const vector<Step> nearby{ Step(0, +1), Step(0, -1), Step(+1, 0), Step(-1, 0) };
    	while (!q.empty()) {
    		Coords ij = q.front();
    		auto i1 = ij.first, j1 = ij.second;
    		q.pop();
    		for (Step s : nearby) {
    			ptrdiff_t i2 = i1 + s.first, j2 = j1 + s.second;
    			if (get(i2, j2)) {
    				if (!visited[i2][j2]) {
    					visited[i2][j2] = true;
    					q.push(Coords(i2, j2));
    				}
    			} else {
    				border.insert(BorderPiece(i1, j1, i2, j2));
    			}
    		}
    	}
    	return border.size();
    }
    

  • 0
    A

    @SergeyTachenov
    This seems like a really good approach to me. However I am unclear why the 3rd example has circumference of 5. Shouldn't it be 13 ? Also, i was assuming that with this approach you are going to pad the entire matrix with 0's all around (or at least logically). I am not sure if you have implemented that way. But that would definitely work.

    Here is how I solved it:
    Key Observation:
    In an island how many units can a single 1 contribute ?

    0000
    0100
    0000
    

    In this case the only 1 contributes 4 (= the actual circumference)

    0000
    0110
    0000
    

    In this case the each 1 contributes 3 (the actual circumference = 6)

    0000
    0110
    0010
    

    In this case the two 1's contributes 3 and one of them contributes 2 (the actual circumference = 8)

    Lastly,

    0010
    0111
    0010
    

    In this case the all 1's contributes 3 and the middle one contributes 0 (the actual circumference = 12)

    Now, contribution for any 1 = max degree (=4) - actual outdegree (You can confirm that from all the examples)

    So basically algorithm is :

    1. Perform dfs/bs
    2. while visiting each node count its outdegree and compute contribution => add it to total circumference

  • 0

    @ayushpatwari I should have put more dots in there, but the edit function is buggy, and I can't edit now. The thing is, I meant to show only a part of an island, so in the case 3 only the 1s bordering 0s are meaningful, the borders are not borders at all: just imagine one more line of dots below the whole thing.

    In my implementation, I did pad the matrix with 0s around: note that the get lambda returns false in case when i or j is outside the area.

    Your approach is essentially the same, but without keeping the border pieces in the set. As a matter of fact, I don't have to either! You basically sum up 4 - count of 1s, but it's the same as summing up count of 0s (assuming the matrix is surrounded by 0s). And that's exactly what I do, so I don't even need a set because I never ever try to insert the same thing into it (because i1, j1 are unique). Therefore, the size of set will be equal to the number of insert calls, so I can just count them without actually inserting anything anywhere.

    One more interesting observation. The complexity of the whole thing can be up to O(mn). This is the worst case lower bound because in the worst case an island may be a very narrow snake-like windy thing with its circumference of order mn. But in the best case, when an island has relatively normal shape, we can do much better if we can just go in a random direction, hit the island's border, and then just walk around. It can get as good as O(m + n). It's easier said than done, though, because walking around will involve a lot of edge cases.

    This idea raises an important question, though: can an island have “lakes” inside? Because if it can, the improved approach won't work. But then again, our current approach will calculate the total circumference of all shores, both inner and outer, which may or may not be what we want.

    On a side note, I think your original problem example has a small mistake: the last case should be (4, 2), not (4, 1) because (4, 1) points to a 0.


  • 0
    D

    I'm not understanding how you guys are counting the perimeter. For example:

    01110
    00<1>10
    11001
    01010
    ```
    
    The value at (2,3) i've put < > around, if I understand the coordinate system correctly. Now counting the 1's around it, we have:
    3 1's in the first row
    1 1's in the 2nd row
    3 1's in the 3rd row
    
    which gives us a total of 7 surrounding ones. How did you arrive at 10?
    
    -Thanks

  • 0
    R

    Do BFS or DFS and sum up the number of non diagonally adjacent 0's for every 1 on the island. Edges of the matrix should also be considered as 0's.


  • 0
    A

    @dat.vikash The problem is to find the perimeter, not the number of surrounding one's. I think drawing a diagram and marking out the island will help. Also you can check this problem which was added recently : https://leetcode.com/problems/island-perimeter/


Log in to reply
 

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