Rewarding XP for my West Marches game

The way I've awarded XP in the past is by, like everyone else, giving it out by slaying monsters. But what I've found is that by making that the only way the characters can gain xp, the players in question get this murder-hobo mentality... where they feel they need to murder EVERYTHING in their path. It's incredibly fucking annoying. It's one of the few things about dungeons and dragons I highly dislike. I have eradicated that way of thinking from my table. It's really difficult at first, but it soon becomes a habit. The way I now award XP is solely through exploration. Yes, crazy right? "So you just go somewhere and you get some XP and level up?" Yes and no. There are a few steps that make this work, and they are as follows:

Step 1: Discover a location and plot the point on the map

Gaining discovery XP is a 2 step process. The first thing the PC's must do to acquire ANY kind of XP is:

1. Discover the location. That means getting close enough to it that they can easily make out what it is they're discovering. 'Is it a pile of rubble in the distance or is it the remains of a castle? Nah, it's rubble.'
2. Once they do so, they need to record it on their shared map. It doesn't even have to be accurate. You, the referee, know exactly where it's at. Doesn't mean they have to. But, they should be involved in the game world. This earns each character the discovery portion of the XP. This is probably the easiest, and quite possibly the most broken part of my rules... but I'm okay with it, because they're mine. 

Note: Traveling is and should be really dangerous, especially at lower levels. The world's a big place, they risk a lot by leaving the relative safety of the city walls. Let the players feel it so they don't take advantage of the discovery system.

Step 2: Explore the location

The PC's need to fully... and I mean fully explore the entire location, leaving no stone left unturned. OR, if applicable, make peace(LOL) and some sort of a treaty or agreement with whatever denizens that dwell within the given location. Maybe it means 'killing the carrion that infest the lower levels' or 'take this mckguffin to this asshole.' Whatever the case may be, it needs to be an agreement of some sort. If that falls through, which it very well may, then revert back to the 'leaving no stone left unturned' bit, because they aren't getting XP, and I'm sure the fighter of the group is waiting for that to happen. To expand on this, make the explored location XP fucking challenging. That's a ton of XP. Make them fight for it if they want to fight.

Step 3: Make it back to their home base with the loot

It's as simple as that, navigate back through the forest, desert... whatever, and bring home that bacon. Don't play games with the PC's either. They ran through your little gauntlet, they earned it. If they have the proper amount of gold(and time), they level up. If not, go back out, earn more gold and XP.

Note: Use your best judgement when determining what is discovery and explored. Typically, places with one to two rooms or outside man-made features ONLY count as discovery, unless they're massive and take time to explore. The word explored is the key word; if the characters can just happen upon it and walk away, that would be discovery. If they need to take time to explore it fully, that would be exploration. Again, use your judgement. 

Below is the table I use for dividing out XP. Each area in a given region has a challenge rating associated with it. Each location has an XP amount associated with it based on the challenge rating of that region. The experience noted may seem like a lot, but the players have to work their asses off to earn it. Usually someone, if not all of them, ends up dead. It's totally worth it in the end. The mortality rates for my games are pretty high. If you have a softer group, lower the xp thresholds. However, I'd give something like this a shot. It'll change how the table operates. It's a nice change of pace. Give it a shot and tell me how it goes.

Furthermore, here is my West Marches hack for 5e that should tie this all together. Enjoy.

Experience Points by Location

CR 1-2

Discovering Location 75xp

Explored Location 225xp

|

CR 3-4

Discovering Location 200xp

Explored Location 400xp

|

CR 5-6

Discovering Location 2825 xp

Explored Location 8475 xp

|

CR 7-8

Discovering Location 5000xp

Explored Location 15,000xp

|

CR 9-10

Discovering Location 7,500xp

Explored Location 22,500xp

|

CR 11-12

Discovering Location 9,000xp

Explored Location 27,000xp

|

CR 13-14

Discovering Location 10,000xp

Explored Location 30,000xp

|

CR 15-16

Discovering Location 13,750xp

Explored Location 41,250

|

CR 17-18

Discovering Location 17,500xp

Explored Location 52,000xp

|

CR 19-20

Discovering Location 22,500xp

Explored Location 67,500xp