Massive Algorithms: MatrixCode

MatrixCode – Moonstone
http://www.1point3acres.com/bbs/thread-189039-1-1.html
3 写一个function，输入一个char[][], 一个int len。char[][] 里每个字符都是distinct的。输出int count。
count 的含义是 char array 里能生成的所有长度为len的code的个数。
code 的含义是可以通过char[][] 生成的字符串。code里的下一个字符可以是当前字符的上/下/左/右字符，也可以是它自己。但是不能是'*'或者'#'。
举个例子：
input:
char[][]:
a b c
d e f
* # x
len: 2
可能的code有：
aa, ab, ad, bb, ba, bc, be, cc, cb, cf, dd, da, de, ee, eb, ed, ef, ff, fc, fe, fx, xx
一共22个可能的code，
输出 count = 22。

一开始的解法穷举所有可能性。后来发现用dp可以做。

建一个memo
如果长度是一，所有位置都是一。
如果长度是二，每一个位置都是上一步中自己＋上＋下＋左＋右。
。。。。
是因为每一步时每个位置只纪录从自己开始的。

memo + DP, 例如：
a, b,
c, d
先考虑长度是1，那只能是每个字母自己，
1, 1
1, 1
长度是2的时候，对a来说可以是a ＋（a, b, c), 是3
3，3
3，3
长度是3的时候，对a来说可以是a + (aa, ab, ac), a + (b 和 c 长度是2 的变化）
9，9
9，9

public List<string> MatrixCode(char[,] matrix, int len)

{

    List<string> result = new List<string>();

    if ((matrix == null) || (len <= 0))

    {

        return result;

    }

    int R = matrix.GetLength(0);

    int C = matrix.GetLength(1);

    Dictionary<Tuple<int, int>, List<string>> dict = new Dictionary<Tuple<int, int>, List<string>>();

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

    {

        for (int c = 0; c < C; c++)

        {

            if((matrix[r, c] != '*') && (matrix[r, c] != '#'))

            {

                int index = r * R + c;

                Tuple<int, int> key = new Tuple<int, int>(index, 1);

                dict.Add(key, new List<string>());

                dict[key].Add(matrix[r, c].ToString());

            }

        }

    }

    int[] dirX = new int[] { 0, 0, -1, 0, 1 };

    int[] dirY = new int[] { 0, -1, 0, 1, 0 };

    for (int k = 2; k <= len; k++)

    {

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

        {

            for (int c = 0; c < C; c++)

            {

                int index = r * R + c;

                if ((matrix[r, c] != '*') && (matrix[r, c] != '#'))

                {

                    Tuple<int, int> key = new Tuple<int, int>(index, len);

                    if (!dict.ContainsKey(key))

                    {

                        dict.Add(key, new List<string>());

                    }

                    for (int i = 0; i <= 4; i++)

                    {

                        int m = r + dirX[i];

                        int n = c + dirY[i];

                        if ((m >= 0) && (m < R) && (n >= 0) && (n < C) &&

                            (matrix[m, n] != '*') && (matrix[m, n] != '#'))

                        {

                            Tuple<int, int> subKey = new Tuple<int, int>(m * R + n, k - 1);

                            if (dict.ContainsKey(subKey))

                            {

                                List<string> subValue = dict[subKey];

                                foreach (var s in subValue)

                                {

                                    string str = matrix[r, c] + s;

                                    if (!dict[key].Contains(str))

                                    {

                                        dict[key].Add(str);

                                    }

                                }

                            }

                        }

                    }

                }

            }

        }

    }

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

    {

        for (int c = 0; c < C; c++)

        {

            Tuple<int, int> key = new Tuple<int,int>(r * R + c, len);

            if (dict.ContainsKey(key))

            {

                result.AddRange(dict[key]);

            }

        }

    }

    return result;

}

另问第三题如何用dp做,只写了dfs的
void codeString(set<string> &s, vector<vector<char>> vv, int len, int x, int y, string curStr)
{
if (x < 0 || y < 0 || x >= (int)vv.size() || y >= (int)vv[0].size() || curStr.size() > len || vv[x][y] == '#' || vv[x][y] == '*')return;
if (s.find(curStr) == s.end() && (int)curStr.size() == len)
{
s.insert(curStr);
return;
}
codeString(s, vv, len, x, y, curStr + vv[x][y]);
codeString(s, vv, len, x + 1, y,  curStr + vv[x][y]);
codeString(s, vv, len, x, y + 1,  curStr + vv[x][y]);
codeString(s, vv, len, x - 1, y,  curStr + vv[x][y]);
codeString(s, vv, len, x, y - 1,  curStr + vv[x][y]);
}
Read full article from MatrixCode – Moonstone

MatrixCode – Moonstone

Labels

Popular Posts