using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4");
WillReturn.Add("3 4");
WillReturn.Add("ABCB");
WillReturn.Add("CACC");
WillReturn.Add("BCBA");
WillReturn.Add("2 2");
WillReturn.Add("CB");
WillReturn.Add("AA");
WillReturn.Add("1 10");
WillReturn.Add("BCBCBCBCBC");
WillReturn.Add("10 10");
WillReturn.Add("CCAABACAAA");
WillReturn.Add("CCCBACACCA");
WillReturn.Add("BACAABCBBA");
WillReturn.Add("ACCCAACCCA");
WillReturn.Add("CCAAAACCBA");
WillReturn.Add("AACBBACCAA");
WillReturn.Add("BCCCACBBAB");
WillReturn.Add("CBBCAACCCC");
WillReturn.Add("CBBCCBCBCA");
WillReturn.Add("BBACABBACC");
//0
//2
//10
//5
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => int.Parse(pX)).ToArray();
}
static char[,] mBanArr;
static int UB_X;
static int UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
int CurrInd = 1;
var sb = new System.Text.StringBuilder();
while (true) {
int[] wkArr = GetSplitArr(InputList[CurrInd]);
int H = wkArr[0];
var StrList = new List<string>();
for (int I = CurrInd + 1; I <= CurrInd + 1 + H - 1; I++) {
StrList.Add(InputList[I]);
}
mBanArr = CreateBanArr(StrList);
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
long Answer = Solve();
sb.Append(Answer);
sb.AppendLine();
CurrInd += 1 + H;
if (CurrInd > InputList.Count - 1) break;
}
Console.Write(sb.ToString());
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int VectX;
internal int VectY;
internal int Cost;
}
static int Solve()
{
var InsLinkedList = new LinkedList<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrX = 0;
WillEnqueue.CurrY = 0;
WillEnqueue.VectX = 1;
WillEnqueue.VectY = 0;
WillEnqueue.Cost = 0;
InsLinkedList.AddFirst(WillEnqueue);
var EdakiriDict = new Dictionary<long, int>();
int Answer = int.MaxValue;
while (InsLinkedList.Count > 0) {
JyoutaiDef Dequeued = InsLinkedList.First.Value;
InsLinkedList.RemoveFirst();
if (Dequeued.Cost >= Answer) continue;
// A,B,Cと、コストの増加有無を指定
Action<char, bool> EnqueueAct = (pPattern, pIsAddCost) =>
{
int NewVectX = Dequeued.VectX;
int NewVectY = Dequeued.VectY;
// Bの場合の、変位ベクトルの回転処理
if (pPattern == 'B') {
if (Dequeued.VectX == 0 && Dequeued.VectY == -1) {
NewVectX = -1; NewVectY = 0;
}
if (Dequeued.VectX == 0 && Dequeued.VectY == 1) {
NewVectX = 1; NewVectY = 0;
}
if (Dequeued.VectX == -1 && Dequeued.VectY == 0) {
NewVectX = 0; NewVectY = -1;
}
if (Dequeued.VectX == 1 && Dequeued.VectY == 0) {
NewVectX = 0; NewVectY = 1;
}
}
// Cの場合の、変位ベクトルの回転処理
if (pPattern == 'C') {
if (Dequeued.VectX == 0 && Dequeued.VectY == -1) {
NewVectX = 1; NewVectY = 0;
}
if (Dequeued.VectX == 0 && Dequeued.VectY == 1) {
NewVectX = -1; NewVectY = 0;
}
if (Dequeued.VectX == -1 && Dequeued.VectY == 0) {
NewVectX = 0; NewVectY = 1;
}
if (Dequeued.VectX == 1 && Dequeued.VectY == 0) {
NewVectX = 0; NewVectY = -1;
}
}
WillEnqueue.CurrX = Dequeued.CurrX + NewVectX;
WillEnqueue.CurrY = Dequeued.CurrY + NewVectY;
WillEnqueue.VectX = NewVectX;
WillEnqueue.VectY = NewVectY;
if (pIsAddCost) {
WillEnqueue.Cost = Dequeued.Cost + 1;
}
else {
WillEnqueue.Cost = Dequeued.Cost;
}
if (WillEnqueue.CurrX == UB_X + 1 && WillEnqueue.CurrY == UB_Y) {
Answer = Math.Min(Answer, WillEnqueue.Cost);
return;
}
if (WillEnqueue.CurrX < 0 || UB_X < WillEnqueue.CurrX) return;
if (WillEnqueue.CurrY < 0 || UB_Y < WillEnqueue.CurrY) return;
long Hash = GetHash(WillEnqueue);
if (EdakiriDict.ContainsKey(Hash)) {
if (EdakiriDict[Hash] <= WillEnqueue.Cost) {
return;
}
}
EdakiriDict[Hash] = WillEnqueue.Cost;
if (pIsAddCost) {
InsLinkedList.AddLast(WillEnqueue);
}
else {
InsLinkedList.AddFirst(WillEnqueue);
}
};
if (mBanArr[Dequeued.CurrX, Dequeued.CurrY] == 'A') {
EnqueueAct('A', false);
EnqueueAct('B', true);
EnqueueAct('C', true);
}
if (mBanArr[Dequeued.CurrX, Dequeued.CurrY] == 'B') {
EnqueueAct('A', true);
EnqueueAct('B', false);
EnqueueAct('C', true);
}
if (mBanArr[Dequeued.CurrX, Dequeued.CurrY] == 'C') {
EnqueueAct('A', true);
EnqueueAct('B', true);
EnqueueAct('C', false);
}
}
return Answer;
}
static long GetHash(JyoutaiDef pJyoutai)
{
long Hash = pJyoutai.CurrX;
Hash *= 1000000;
Hash += pJyoutai.CurrY;
Hash *= 10;
Hash += pJyoutai.VectX + 2;
Hash *= 10;
Hash += pJyoutai.VectY + 2;
return Hash;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をcharの2次元配列に設定
////////////////////////////////////////////////////////////////
static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new char[0, 0];
}
int UB_X = StrList[0].Length - 1;
int UB_Y = StrList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = StrList[Y][X];
}
}
return WillReturn;
}
}