You can only find the minimum number of gates in a multi-level network by solving an integer programming problem [or equivalents, see below]. This problem is NP-complete, so only practical to solve up to a dozen gates or so.
There exist approximation methods that won't give you the minimum number but are more tractable in terms of time required... These are a vast topic in themselves, basically the whole field of multi-level optimization. You can read a [free] overview here.
For small networks of NAND (up to 4 variables), the problem has been completely solved by exhaustive enumeration [or equivalent methods]. There's a fairly recent [2009] PhD thesis by Elizabeth Ann Ernst that summarizes the ancient results and extends them. Ernst uses branch-and-bound, which improves upon the exhaustive method in practice, but not asymptotically. She also notes that other implicit enumeration methods like integer programming or CSP (constraint satisfaction, solved via SAT) perform worse in practice.
She obviously wrote some software for her method (called BESS), but I'm not sure if it's publicly available somewhere. Full text of her thesis is freely available at umich. And indeed you found the minimal expression for 2-input xor (your 2nd one obviously), the one highlighted below:
She also compared the exact results (for NANDs) with those produced by the heuristic optimizer from ABC.
ABC was able to produce an optimal network for 340 out of 4,043 functions where the optimal network is known. For those functions where ABC did not produce an optimal network it was an average of 36% larger than the optimal network[.]
There (obviously) some [larger] networks for which BESS didn't finish, but allowed an upper bound to be found (at the point where the search was abandoned). For those ABC did quite well [well with respect to the bounds found], as you can see from the 2nd graph below.
To answer the 2nd part of your question: K-map representations connect from top to bottom, and left edge to right edge- so the outer 4 corners are all part of one adjacency group, A' (This means you can derive A' + BC directly)
Best Answer
This is not a feature of any schematic drawing package that I am aware of. The answer is therefore probably "you can't". You have to delete the existing diagram and re-draw it using different gates.
This seems to be especially true since your diagram appears to be ASCII art intead of drawn with something that understands the underlying logic functions.
Just re-draw it.