First, my math skills suck.

However, I'm pretty good with logic (believe it or not!)

Second, let's define the "mess." Multiple river/road crossing in a single block are bad, right? But, in reality, chances are there will be at least one crossing in any given block. So the issue is finding the balance, right?
Ok, we start with a block that has rivers and roads on it. It sounds like CATE knows if there's an E-W orientation or N-S. I think the problem comes where there's a N-S road and a N-S river - too many tiles are right next to each other. So first, I think we need to figure out where the river is in relation to the road on each edge. So, if the river is E of the road on the N edge and E of the river on the S edge, then no crossing at all - they parallel each other. If the river is W of the road on the N edge but E of the road on the S edge, then there should be one crossing, maybe right in the middle.
Is this kinda what we need to work out?