I would use a loop to check each pixel from the sprite's origin point (his feet) upwards for the height of the sprite, checking to see if there is a wall there (either because its a region or because it's not a walkable area). If you don't find one, the sprite is fine where it is. If you do find one you take the number of pixels you've searched, subtract it from the sprite's height and move the sprite that number down the screen.
For example if your sprite is 100 pixels tall and starts overlapping a wall 80 pixels above its feet, the top 20 pixels (100 - 80) are going through the wall. You would then move the spite down 20 pixels. Of course this assumes all the corridors are at least the sprite's height, otherwise his feet will overlap a wall instead.
You could search every pixel for an overlap, but that might be slow. Instead you could search a column going upwards from the middle of the sprite, and/or each side of the spite. You could also only check every x number of pixels going up, as long as your walls are less than x pixels wide.
