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做,只写了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]);. 1point3acres.com/bbs
}
Read full article from 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
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]);. 1point3acres.com/bbs
}
Read full article from MatrixCode – Moonstone