Kory.xml

<?xml version="1.0" encoding="utf-8" ?>
<root>
  <players>
    <player name="Pam" >
      <tile terrain="B" cost="1" />
      <tile terrain="Z" cost="2" />
      <tile terrain="N" cost="2" />
      <tile terrain="M" cost="2" />
      <tile terrain="P" cost="5" />
    </player>
    <player name="Dwight" >
      <tile terrain="B" cost="3" />
      <tile terrain="Z" cost="3" />
      <tile terrain="N" cost="2" />
      <tile terrain="M" cost="5" />
      <tile terrain="P" cost="4" />
    </player>
    <player name="Jim" >
      <tile terrain="B" cost="5" />
      <tile terrain="Z" cost="1" />
      <tile terrain="N" cost="1" />
      <tile terrain="M" cost="7" />
      <tile terrain="P" cost="6" />
    </player>
    <player name="Kelly" >
      <tile terrain="B" cost="4" />
      <tile terrain="Z" cost="1" />
      <tile terrain="N" cost="5" />
      <tile terrain="M" cost="4" />
      <tile terrain="P" cost="4" />
      <tile terrain="Q" cost="2" />
    </player>
  </players>
  <map>
    <row>$OPBONOQM</row>
    <row>O*B*Q*Z*P</row>
    <row>NOOOPPZMZ</row>
    <row>N*N*O*P*O</row>
    <row>PBQOQOQOB</row>
    <row>M*Q*Z*M*Q</row>
    <row>NPQMQOQMN</row>
    <row>M*M*Q*M*B</row>
    <row>POPBBBPB@</row>
  </map>
</root>

PathSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml;

namespace PathSolver
{
    class Program
    {
        static void Main(string[] args)
        {
            var game = LoadXml("Kory");
            game.CalculatePlayersCost();
            var winner = game.Players.OrderBy(x => x.TotalMoveCost).First();
            Console.WriteLine($"Name: {winner.Name}, Cost: {winner.TotalMoveCost}");
            Console.WriteLine("Moves:");
            Console.WriteLine(winner.GetPath());
        }

        static public Game LoadXml(string fileName)
        {
            var game = new Game();
            XmlDocument doc = new XmlDocument();
            doc.Load(fileName);
            XmlNodeList players = doc.SelectNodes("/root/players/player");
            foreach (XmlNode player in players)
            {
                var domainPlayer = new Player();
                domainPlayer.Name = player.Attributes["name"].Value;

                foreach (XmlNode tile in player.ChildNodes)
                {
                    var domainTile = new Tile();
                    domainTile.Terrain = Convert.ToChar(tile.Attributes["terrain"].Value);
                    domainTile.Cost = Int32.Parse(tile.Attributes["cost"].Value);
                    domainPlayer.Tiles.Add(domainTile);
                }


                game.Players.Add(domainPlayer);
            }
            XmlNodeList rows = doc.SelectNodes("/root/map/row");
            int irow = 0; 
            int icol = 0;
            bool flag = false;
            foreach (XmlNode row in rows)
            {
                string mapTiles = row.InnerText;
                if (!flag)
                {
                    game.Board = new char[row.InnerText.Length, row.InnerText.Length];
                    flag = true;
                }
                
                foreach (var tile in mapTiles)
                    game.Board[irow,icol++] = tile;
                icol = 0;
                irow++;
            }
            return game;
        }
    }

    public class Player
    {
        public string Name { get; set; }
        public int TotalMoveCost { get; set; }
        public List<Move> Moves { get; set; }

        public List<Tile> Tiles { get; set; } = new List<Tile>();

        public int GetCostForTile(char tile)
            => Tiles.FirstOrDefault(x => x.Terrain == tile)?.Cost ?? 1;

        public string GetPath()
            => string.Join(Environment.NewLine, Moves.Select(m => $"=> ({m.Row}, {m.Col}), {m.Cost}"));
    }

    public class Tile
    {
        public char Terrain { get; set; }
        public int Cost { get; set; }
    }

    public class Move
    {
        public int Cost { get; set; }
        public int Row { get; set; }
        public int Col { get; set; }

        public Move(int row, int col, int cost)
        {
            Row = row;
            Col = col;
            Cost = cost;
        }
    }

    public class Game
    {
        public List<Player> Players { get; set; }
        public char[,] Board { get; set; }
        private int _length;

        public Game()
        {
            Players = new List<Player>();
        }

        public void CalculatePlayersCost()
        {
            foreach (var player in Players)
                CalculateCost(player);
        }

        private void CalculateCost(Player player)
        {
            int length = Board.GetLength(0);
            _length = length;
            var previousPositions = new List<(int row, int col)>();
            var bestPath = CalculateRecurse(player, previousPositions, 0, 0);
            player.TotalMoveCost = bestPath.cost;
            player.Moves = bestPath.moves.AsEnumerable().Reverse().ToList();
        }

        private (int cost, List<Move> moves) CalculateRecurse(Player player, List<(int row, int col)> previousPositions, int row, int col)
        {
            var positions = GetAvailablePositions(previousPositions, row, col);

            var pos = positions.FirstOrDefault(x => x.tile == '@');
            if (positions.Any(x => x.tile == '@'))
                return (1, new List<Move> { new Move(pos.row, pos.col, 1) });

            var costs = new List<(int, List<Move>)>();
            var moves = GetBestMoves(player, positions.Select(x => x.tile).ToList());
            foreach (var position in moves)
            {
                // update previous state so we don't visit again
                previousPositions = previousPositions.Concat(new [] { (row, col) }).ToList();

                // move to new position
                var nextMove = positions.First(x => x.tile == position.tile);
                row = nextMove.row;
                col = nextMove.col;
                
                // remove the selected move from the list of available positions
                positions.Remove(nextMove);

                var pathCost = CalculateRecurse(player, previousPositions, row, col);

                // add the costs for choices that end up succesfully completing the maze
                if (pathCost.cost > 0)
                    costs.Add((pathCost.cost + position.cost, 
                        pathCost.moves.Concat(new[] { new Move(row, col, pathCost.cost) }).ToList()));
            }

            if (costs.Count > 0)
                return costs.OrderBy(x => x.Item1).First();

            return (0, null);
        }

        private List<(char tile, int row, int col)> GetAvailablePositions(List<(int row, int col)> previousPositions, int row, int col)
        {
            int right = col + 1;
            int up = row - 1;
            int down = row + 1;
            int left = col - 1;
            List<(char title, int row, int col)> tiles = new List<(char title, int row, int col)>();
            

            if (right < _length && !IsPrevious(previousPositions, row, right) && IsValid(Board[row, right]))
                tiles.Add((Board[row, right], row, right));

            if (left >= 0 && !IsPrevious(previousPositions, row, left) && IsValid(Board[row, left]))
                tiles.Add((Board[row, left], row, left));

            if (up >= 0 && !IsPrevious(previousPositions, up, col) &&  IsValid(Board[up, col]))
                tiles.Add((Board[up, col], up, col));

            if (down < _length && !IsPrevious(previousPositions, down, col) && IsValid(Board[down, col]))
                tiles.Add((Board[down, col], down, col));

            return tiles;
        }

        private bool IsValid(char tile)
            => tile != '*';

        private bool IsPrevious(List<(int row, int col)> previous, int row, int col)
            => previous.Any(x => x.row == row && x.col == col);

        private bool IsLastBacktracked(List<(int row, int col)> last, int row, int col)
            => last.Any(x => x.row == row && x.col == col);

        private List<(char tile, int cost)> GetBestMoves(Player player, List<char> positions)
        {
            return positions.Select(pos => (tile: pos, cost: player.GetCostForTile(pos))).OrderBy(x => x.cost).ToList();
        }
    }
}

Name: Pam, Cost: 19
Moves:
=> (1, 0), 18
=> (2, 0), 16
=> (2, 1), 15
=> (2, 2), 14
=> (3, 2), 12
=> (4, 2), 11
=> (4, 3), 10
=> (4, 4), 9
=> (4, 5), 8
=> (4, 6), 7
=> (4, 7), 6
=> (4, 8), 5
=> (5, 8), 4
=> (6, 8), 2
=> (7, 8), 1
=> (8, 8), 1