Thursday, June 9, 2016

MatrixCode – Moonstone

MatrixCode – Moonstone
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

aa, ab, ad, bb, ba, bc, be, cc, cb, cf, dd, da, de, ee, eb, ed, ef, ff, fc, fe, fx, xx

。。。。

memo + DP, 例如：. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
a, b,
c, d

1, 1
1, 1

3，3
3，3

9，9
9，9

 `public List MatrixCode(char[,] matrix, int len)` `{` `    ``List result = new List();` `    ``if ((matrix == null) || (len <= ``0``))` `    ``{` `        ``return result;` `    ``}` `    ``int R = matrix.GetLength(``0``);` `    ``int C = matrix.GetLength(``1``);` `    ``Dictionary, List> dict = new Dictionary, List>();` `    ``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 key = new Tuple(index, ``1``);` `                ``dict.Add(key, new List());` `                ``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 key = new Tuple(index, len);` `                    ``if (!dict.ContainsKey(key))` `                    ``{` `                        ``dict.Add(key, new List());` `                    ``}` `                    ``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 subKey = new Tuple(m * R + n, k - ``1``);` `                            ``if (dict.ContainsKey(subKey))` `                            ``{` `                                ``List 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 key = new Tuple(r * R + c, len);` `            ``if (dict.ContainsKey(key))` `            ``{` `                ``result.AddRange(dict[key]);` `            ``}` `        ``}` `    ``}` `    ``return result;` `}`

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]);. 1point3acres.com/bbs
}