l********o
发帖数: 56 | 1 刚刚跪了。。大家看看这道题有什么好方法吗？
给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
是否valid
Note：A N C, A NE C同时出现是合法的
例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
A N C
B NE C
C NE D
A S D
B W A | k******i
发帖数: 11 | | I*******g
发帖数: 7600 | 3 建树 BFS 如果下一个建树出现矛盾就非法
direction
【在 l********o 的大作中提到】
: 刚刚跪了。。大家看看这道题有什么好方法吗？
: 给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
: 是否valid
: Note：A N C, A NE C同时出现是合法的
: 例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
: A N C
: B NE C
: C NE D
: A S D
: B W A
| l********o
发帖数: 56 | 4 能说详细点儿吗？
【在 I*******g 的大作中提到】
: 建树 BFS 如果下一个建树出现矛盾就非法
:
: direction
| r****7
发帖数: 2282 | 5 有向图，带环就invalid，不带环就valid | l********o
发帖数: 56 | | g*******0
发帖数: 20 | 7 两个方向就够了
【在 l********o 的大作中提到】
: 四个方向找环是正解。。 学习了
| d****e
发帖数: 251 | 8 有环没环不是问题。取决于这个题目是否是基于简单的网格系统。
如果是，你可以用一个简单的hash map，检查是否有冲突的坐标。时间复杂度O(n)
否者，我们得知道怎么判断冲突，譬如在这里，is A NE D? 这个就更复杂了。 | b******i
发帖数: 914 | 9 x, y两个方向建立一个关系map，然后bfs或者dfs map找有没有环
direction
【在 l********o 的大作中提到】
: 刚刚跪了。。大家看看这道题有什么好方法吗？
: 给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
: 是否valid
: Note：A N C, A NE C同时出现是合法的
: 例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
: A N C
: B NE C
: C NE D
: A S D
: B W A
| l********o
发帖数: 56 | 10 刚刚跪了。。大家看看这道题有什么好方法吗？
给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
是否valid
Note：A N C, A NE C同时出现是合法的
例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
A N C
B NE C
C NE D
A S D
B W A | | | k******i
发帖数: 11 | | I*******g
发帖数: 7600 | 12 建树 BFS 如果下一个建树出现矛盾就非法
direction
【在 l********o 的大作中提到】
: 刚刚跪了。。大家看看这道题有什么好方法吗？
: 给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
: 是否valid
: Note：A N C, A NE C同时出现是合法的
: 例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
: A N C
: B NE C
: C NE D
: A S D
: B W A
| l********o
发帖数: 56 | 13 能说详细点儿吗？
【在 I*******g 的大作中提到】
: 建树 BFS 如果下一个建树出现矛盾就非法
:
: direction
| r****7
发帖数: 2282 | 14 有向图，带环就invalid，不带环就valid | l********o
发帖数: 56 | | g*******0
发帖数: 20 | 16 两个方向就够了
【在 l********o 的大作中提到】
: 四个方向找环是正解。。 学习了
| d****e
发帖数: 251 | 17 有环没环不是问题。取决于这个题目是否是基于简单的网格系统。
如果是，你可以用一个简单的hash map，检查是否有冲突的坐标。时间复杂度O(n)
否者，我们得知道怎么判断冲突，譬如在这里，is A NE D? 这个就更复杂了。 | b******i
发帖数: 914 | 18 x, y两个方向建立一个关系map，然后bfs或者dfs map找有没有环
direction
【在 l********o 的大作中提到】
: 刚刚跪了。。大家看看这道题有什么好方法吗？
: 给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
: 是否valid
: Note：A N C, A NE C同时出现是合法的
: 例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
: A N C
: B NE C
: C NE D
: A S D
: B W A
| h******e
发帖数: 52 | 19 Solution: use hashtable, the key is the letter and the value is pair of (x,
y), where x and y could be -1, 0, +1. We can choose one in the beginning as
(0, 0).
Example
A N C -> C(0, 0) A(0, +1) we choose C as (0, 0)
B NE C -> B is not in table yet, add B(+1, +1)
C NE D -> D is not in table yet, add D(-1, -1)
A S D -> both A and D are in table. A S D requires A.y < D.y. However A.y ==
+1 and D.y == -1. So it is not true.
B W A -> requires B.x < A.x, however B.x == +1 and A.x == 0 which is not
true
欢迎指正！ | l*****a
发帖数: 14598 | 20 如果是
A N C
D N E
你打算如何给D/E确定坐标呢？
,
as
==
【在 h******e 的大作中提到】
: Solution: use hashtable, the key is the letter and the value is pair of (x,
: y), where x and y could be -1, 0, +1. We can choose one in the beginning as
: (0, 0).
: Example
: A N C -> C(0, 0) A(0, +1) we choose C as (0, 0)
: B NE C -> B is not in table yet, add B(+1, +1)
: C NE D -> D is not in table yet, add D(-1, -1)
: A S D -> both A and D are in table. A S D requires A.y < D.y. However A.y ==
: +1 and D.y == -1. So it is not true.
: B W A -> requires B.x < A.x, however B.x == +1 and A.x == 0 which is not
| | | p*****2
发帖数: 21240 | 21
大牛准备出山了？
【在 l*****a 的大作中提到】
: 如果是
: A N C
: D N E
: 你打算如何给D/E确定坐标呢？
:
: ,
: as
: ==
| d******e
发帖数: 2265 | 22 建片叙关系
如果 A S D 改成 D-> A.A n c 改为 A-> C
这题是不是见过了？
direction
【在 l********o 的大作中提到】
: 刚刚跪了。。大家看看这道题有什么好方法吗？
: 给一串direction, 比如A N C 意味着A在C的北边。写一个function验证这些direction
: 是否valid
: Note：A N C, A NE C同时出现是合法的
: 例子：下面这个不合法，因为A N C, C NE D所以不可能A S D
: A N C
: B NE C
: C NE D
: A S D
: B W A
| w****2
发帖数: 6 | 23 问题有些模糊的地方比如什么是合法，怎么推理（A N C）& （C NE D） ＝》 （A ？D
）对这个特殊问题合法性和推理规则也不难定义。
Given d = {N, NE, E, SE, S, SW, W, NW}.
- (d1, d2) is consistent if d1 \cap d2 != \empty
- (A d1 B) (B d2 C) => (A d1 \cap d2 B)
- (A d1 B) => (B d2 A) where d2 is the substitute d1 with S<->N and W<->E
Let D be a n X n matrix (it can be considered a graph) where D(i,j) is a set
of directions from i to j, given or inferred. Then run the inference until
no more changes. During inference, whenever a new direction is inferred for
i and j, check if the new direction is consistent with existing ones.
To make it simpler, consider the given objects an ordered set, then it is
not necessry to consider both (A d1 B) and (B d2 A) though the given (B d2 A
) needs to be converted to (A d1 B)
I think this should work, not sure if it is efficient. | l******s
发帖数: 3045 | 24 像word ladder ii类似的一开始预处理所有近似点的做法，建一个大的依赖map先。
C#测试了几个，单连通图的，多独立连通图的正面反面用例，都通过了。
//directions = {{"A", "N", "C"}, {"B", "NE", "C"}, {"C", "NE", "D"}, {"A", "
S", "D"}, {"B", "W", "A"}}
// AB
// C
// D
// A <- false
private static bool validDirections(IList> directions)
{
int[,] depend = new int[26, 8]; //8 directions 0:N; 1:NE; 2:E; 3:SE; 4:S
; 5:SW; 6:W; 7:NW
for (int i = 0; i < depend.GetLength(0); i++)
for (int j = 0; j < depend.GetLength(1); j++)
depend[i, j] = int.MinValue;
foreach(var dir in directions){ //Building a Dual direction dependency
Map
int p1 = dir[0][0] - 'A', p2 = dir[2][0] - 'A';
switch(dir[1]){
case "N": depend[p2, 0] = p1; depend[p1, 4] = p2; break;
case "NE": depend[p2, 1] = p1; depend[p1, 5] = p2; break;
case "E": depend[p2, 2] = p1; depend[p1, 6] = p2; break;
case "SE": depend[p2, 3] = p1; depend[p1, 7] = p2; break;
case "S": depend[p2, 4] = p1; depend[p1, 0] = p2; break;
case "SW": depend[p2, 5] = p1; depend[p1, 1] = p2; break;
case "W": depend[p2, 6] = p1; depend[p1, 2] = p2; break;
case "NW": depend[p2, 7] = p1; depend[p1, 3] = p2; break;
}
}
int[,] coord = new int[26, 2]; //coord[i, 0] is X, coord[i, 1] is Y
for (int i = 0; i < coord.GetLength(0); i++) coord[i, 0] = coord[i, 1] =
int.MinValue;
return dfsSearch(depend, coord, -1, -1, -1);
}
private static bool dfsSearch(int[,] depend, int[,] coord, int last, int
direct, int cur){
if(last == -1){
for(int i = 0; i < depend.GetLength(0); i++)
for(int j = 0; j < depend.GetLength(1); j++)
if (depend[i, j] != int.MinValue){
coord[i, 0] = coord[i, 1] = 0;
int dep = depend[i, j];
depend[i, j] = int.MinValue;
depend[dep, (j + 4) % 8] = int.MinValue;
if (!dfsSearch(depend, coord, i, j, dep)) return false;
}
}
else{
int x = -1, y = -1;
switch (direct){ //8 directions 0:N; 1:NE; 2:E; 3:SE; 4:S; 5:SW; 6:W
; 7:NW
case 0: x = coord[last, 0] + 1; y = coord[last, 1]; break;
case 1: x = coord[last, 0] + 1; y = coord[last, 1] + 1; break;
case 2: x = coord[last, 0]; y = coord[last, 1] + 1; break;
case 3: x = coord[last, 0] - 1; y = coord[last, 1] + 1; break;
case 4: x = coord[last, 0] - 1; y = coord[last, 1]; break;
case 5: x = coord[last, 0] - 1; y = coord[last, 1] - 1; break;
case 6: x = coord[last, 0]; y = coord[last, 1] - 1; break;
case 7: x = coord[last, 0] + 1; y = coord[last, 1] - 1; break;
}
if (coord[cur, 0] != int.MinValue && (coord[cur, 0] != x || coord[
cur, 1] != y))//validate if all depends match
return false;
coord[cur, 0] = x; coord[cur, 1] = y;
for (int j = 0; j < depend.GetLength(1); j++)
if (depend[cur, j] != int.MinValue){
int dep = depend[cur, j];
depend[cur, j] = int.MinValue;
depend[dep, (j + 4) % 8] = int.MinValue;
if (!dfsSearch(depend, coord, cur, j, dep)) return false;
}
}
return true;
}
【在 l*****a 的大作中提到】
: 如果是
: A N C
: D N E
: 你打算如何给D/E确定坐标呢？
:
: ,
: as
: ==
| p*****2
发帖数: 21240 | | h***s
发帖数: 3 | | M**a
发帖数: 25 | 27 我也觉得是 有向图找环， 比如 A N C 可以转换为 A 的y坐标大于C的y坐标， B NE
C 就是 B 的x和y坐标都大与C的x,y坐标， 然后在这一堆不等式里面找冲突的， 可
以转换成有向图里面是否有环的问题。 |
|
