StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
15036708
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
10
CommunityOwnedDate
CreationDate
2013-02-23T03:28:12.153
FavoriteCount
0
LastActivityDate
2013-02-27T21:25:41.493
LastEditDate
2013-02-27T21:25:41.493
LastEditorUserId
1553090
OwnerUserId
1553090
ParentId
15033555
PostTypeId
2
Score
2
ViewCount
0
LastEditorDisplayName
text
Body
Fun question, with many varied solutions. I've been thinking about it this afternoon and I would go for something like flood-fill with a priority queue (min-heap, perhaps). Let's call it the <code>fence</code>. You'll also want to keep track of which items have been visited. Mark all items as unvisited, initially. Start off by adding all points around the perimeter of your grid to the <code>fence</code>. Now you loop like so: Pop the front item from the <code>fence</code>. You have selected one of the lowest points on the perimeter. <ul> <li>If the item has been visited, discard it and loop again.</li> <li>If it's unvisited, its height becomes your new water level only if it is greater than the current water level.</li> </ul> You now do a flood-fill from that point. You can do this recursively (depth-first), but I will discuss this using an unordered queue (breadth-first). Let's call this queue the <code>flood</code>. You start by pushing the item onto <code>flood</code>. Flooding then goes like this: Loop until there are no items remaining in <code>flood</code>... <ul> <li>Pop an item from <code>flood</code></li> <li>If it is already visited, ignore it and loop again.</li> <li>If the item height is less than or equal to the current water level, compute the height difference and add that to your total volume. Mark the item as visited, then add all unvisited neighbours to <code>flood</code>.</li> <li>If the item height is greater than the current water level, just add it to <code>fence</code>. You'll want to have a way to tell whether the item is already in <code>fence</code> - you don't want to add it again. Maybe you can extend your 'visited' flags to cope with this.</li> </ul> And that's it. Admittedly it was just a thought experiment while I lay around feeling hungover and seedy, but I reckon it's good. <hr> As you requested... Some pseudocode. Initial setup: <pre><code>## Clear flags. Note I've added a 'flooding' flag for each item in map item.visited <- false # true means item has had its water depth added item.fenced <- false # true means item is in the fence queue item.flooding <- false # true means item is in the flooding queue end ## Set up perimeter for each item on edge of map (top, left, right, bottom) push item onto fence end waterlevel <- 0 total <- 0 </code></pre> Now the main chunk of the algorithm <pre><code>while fence has items item <- pop item from fence if item.visited = true then loop again ## Update water level if item.height > waterlevel then waterlevel = item.height ## Flood-fill item using current water level push item onto flood item.flooding <- true while flood has items item <- pop item from flood depth <- waterlevel - item.height if depth >= 0 then # Item is at or below water level. Add its depth to total. total <- total + depth item.visited <- true # Consider all immediate neighbours of item. for each neighbour of item if neighbour.visited = false then if neighbour.flooding = false then push neighbour onto flood neighbour.flooding <- true end end end else # Item is above water item.flooding <- false if item.fenced = false then push item onto fence item.fenced <- true end end end end </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POTips on finding the volume of water in a 3d chess board
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USpaddy
UserOwnerUserId
1. USpaddy
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.