using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    private static readonly string[] map = {

        "---------------",

        "---------------",

        "---------------",

        "---++++--------",

        "---+*++--------",

        "---++++--------",

        "---++++--------",

        "---------------",

        "--------++++---",

        "--------++++---",

        "--------++o+---",

        "--------++++---",

        "---------------",

        "---------------",

        "---------------"

    };

    private static readonly int ROWS = map.Length;

    private static readonly int COLS = map[0].Length;

    private static readonly int N = ROWS * COLS * 2;

​

    public static void Main(string[] args)

    {

        int s = FindNest();

        int t = FindBunker();

​

        int[,] C = ToCapacityMatrix();

        Tuple<int, int[,]> fF = EdmondsKarp(C, s, t);

        int f = fF.Item1;

        int[,] F = fF.Item2;

​

        Console.WriteLine("Requires {0} walls.", f);

        Console.WriteLine();

        WriteWalls(C, F, s);

    }

​

    static void WriteWalls(int[,] C, int[,] F, int s)

    {

        HashSet<int> visited = Flood(C, F, s);

​

        string[] newMap = new string[ROWS];

        for(int r = 0; r < ROWS; ++r)

            newMap[r] = map[r];

​

        for (int u = 0; u < N; u += 2)

            if (visited.Contains(u) && !visited.Contains(u + 1) && C[u, u + 1] > 0)

                newMap[ToRow(u)] = newMap[ToRow(u)].Remove(ToCol(u), 1).Insert(ToCol(u), "W");

​

        for (int r = 0; r < ROWS; ++r)

            Console.WriteLine(newMap[r]);

    }

​

    static HashSet<int> Flood(int[,] C, int[,] F, int s)

    {

        HashSet<int> visited = new HashSet<int>();

        Queue<int> queue = new Queue<int>();

​

        visited.Add(s);

        queue.Enqueue(s);

        while (queue.Count > 0)

        {

            int u = queue.Dequeue();

            for (int v = 0; v < N; ++v)

            {

                if ((C[u, v] - F[u, v]) > 0 && !visited.Contains(v))

                {

                    visited.Add(v);

                    queue.Enqueue(v);

                }

            }

        }

​

        return visited;

    }

​

    static int FindNest()

    {

        for (int row = 0; row < ROWS; ++row)

            for (int col = 0; col < COLS; ++col)

                if (map[row][col] == '*')

                    return ToNodeOut(row, col);

        return -1;

    }

​

    static int FindBunker()

    {

        for (int row = 0; row < ROWS; ++row)

            for (int col = 0; col < COLS; ++col)

                if (map[row][col] == 'o')

                    return ToNodeIn(row, col);

        return -1;

    }

​

    static int[,] ToCapacityMatrix()

    {

        int[,] C = new int[N, N];

        for(int node = 0; node < N / 2; ++node) {

            int row = ToRow(node * 2);

            int col = ToCol(node * 2);

            int nodeIn = ToNodeIn(row, col);

            int nodeOut = ToNodeOut(row, col);

​

            // Set node-internal capacity.

            C[nodeIn, nodeOut] =

                (map[row][col] == '-') ? 1 :

                (map[row][col] == '#') ? 0 :

                int.MaxValue;

​

            // Set neighboring capacities.

            if (row > 0)

                C[ToNodeOut(row - 1, col), nodeIn] = int.MaxValue;

            if (row < ROWS - 1)

                C[ToNodeOut(row + 1, col), nodeIn] = int.MaxValue;

            if (col > 0)

                C[ToNodeOut(row, col - 1), nodeIn] = int.MaxValue;

            if (col < COLS - 1)

                C[ToNodeOut(row, col + 1), nodeIn] = int.MaxValue;

        }

​

        return C;

    }

​

    static int ToRow(int node)

    {

        return node / 2 / COLS;

    }

​

    static int ToCol(int node)

    {

        return node / 2 % COLS;

    }

​

    static int ToNodeIn(int row, int col)

    {

        return (row * COLS + col) * 2;

    }

​

    static int ToNodeOut(int row, int col)

    {

        return (row * COLS + col) * 2 + 1;

    }

​

    static Tuple<int, int[,]> EdmondsKarp(int[,] C, int s, int t)

    {

        int f = 0;

        int[,] F = new int[C.GetLength(1), C.GetLength(1)];

​

        while (true)

        {

            Tuple<int, int[]> mP = BreadthFirstSearch(C, s, t, F);

            int m = mP.Item1;

            int[] P = mP.Item2;

​

            if (m == 0)

                break;

​

            f += m;

            int v = t;

            while (v != s)

            {

                int u = P[v];

                F[u, v] += m;

                F[v, u] -= m;

                v = u;

            }

        }

​

        return new Tuple<int,int[,]>(f, F);

    }

​

    static Tuple<int, int[]> BreadthFirstSearch(int[,] C, int s, int t, int[,] F)

    {

        int[] P = new int[N];

        for (int u = 0; u < N; ++u)

            P[u] = -1;

        P[s] = -2;

​

        int[] M = new int[N];

        M[s] = int.MaxValue;

​

        Queue<int> Q = new Queue<int>();

        Q.Enqueue(s);

        while (Q.Count > 0)

        {

            int u = Q.Dequeue();

            for (int v = 0; v < N; ++v)

            {

                if ((C[u, v] - F[u, v] > 0) && (P[v] == -1))

                {

                    P[v] = u;

                    M[v] = Math.Min(M[u], C[u, v] - F[u, v]);

                    if (v != t)

                        Q.Enqueue(v);

                    else

                        return new Tuple<int, int[]>(M[t], P);

                }

            }

        }

​

        return new Tuple<int, int[]>(0, P);

    }

}

​