valorzard

ValorZard

@valorzard

i like trains

  • any

Aspiring indie game dev. 21. Addicted to comics. Touch-starved. What even is gender anyways?
RPG webcomic thingy: @bunny-rpg

log inask
valorzard
@valorzard

Tonight on leetcode adventures

Tried solving this problem: https://leetcode.com/problems/max-area-of-island/
And I quickly fell into the depths of insanity.
Highlights from my discord rants while trying to solve this problem

  • i couldnt just use a set cuz turns out tuples, pairs, and vectors in c++ are ALL unhashable
    you need to make a custom hasher
  • I attempted to hash the position of the current point of the 2D array we were on, only to find that there is no good way to do so. I ended up doing some weird bitshifting to combine two ints into a single long
  • I also tried a different method of solving this problem by using a separate 2D array of boolean values to indicate if we had searched through that position yet, only to find it its apparently really really hard to pass in a 2D array of variable rows and columns as a parameter into a recursive function without extremely ugly templating
    Also, I should mention I gave up halfway through and attempted to port Neetcode's solution from python into c++ only to end up in implementation hell.
    All in all, I don't really like c++ very much. It's probably the least fun language I've ever used, and I had to use Pascal for three years during middle school.
You must log in to comment.

in reply to @valorzard's post:

valorzard
@valorzard

if anyone cares, here's the solution I did. I mostly ported Neetcode's solution, but its super inefficient because python and c++ DO NOT WORK WITH THE SAME ALGORITHMS : class Solution {
public:
int findAreaOfIsland(int row, int col, const vector<vector>& grid, unordered_set& visited)
{
long position = ((long)(row) << 16) + (long)col;
if(row < 0 || row >= grid.size()
|| col >= grid[0].size() || col < 0
|| grid[row][col] == 0 || visited.find(position) != visited.end())
{
return 0;
}
visited.insert(position);
return 1 + (findAreaOfIsland(row + 1, col, grid, visited) +
findAreaOfIsland(row - 1, col, grid, visited) +
findAreaOfIsland(row, col + 1, grid, visited) +
findAreaOfIsland(row, col - 1, grid, visited));
}
int maxAreaOfIsland(vector<vector>& grid) {
// go down vertically
int area = 0;
unordered_set visited;
for(int row = 0; row < grid.size(); ++row){
// go right horizontally
for(int col = 0; col < grid[row].size(); ++col){
area = max(area, findAreaOfIsland(row, col, grid, visited));
}
}
return area;
}
};

login to reply