m********l
发帖数: 4394 | 1 题目是：
Provided with a grid with shaded cells.
Design a solution that finds the minimal distance to a shaded cell |
b***e
发帖数: 383 | 2 "Design a solution that finds the minimal distance to a shaded cell"
from where? |
q****x
发帖数: 7404 | 3 Provided with a grid with shaded cells.
-- what is shaded cells?
Design a solution that finds the minimal distance to a shaded cell
-- from where?
【在 m********l 的大作中提到】
: 题目是：
: Provided with a grid with shaded cells.
: Design a solution that finds the minimal distance to a shaded cell
|
l*****a
发帖数: 14598 | 4 can't u see it from the image???
just consider the common cases,
give u another of two cells in the graph and get the minimal distance
【在 q****x 的大作中提到】
: Provided with a grid with shaded cells.
: -- what is shaded cells?
: Design a solution that finds the minimal distance to a shaded cell
: -- from where?
|
q****x
发帖数: 7404 | 5
the "cell" could refer to one single grid element, or the cluster as a whole
. in the latter case, what is "distance"?
【在 l*****a 的大作中提到】
: can't u see it from the image???
: just consider the common cases,
: give u another of two cells in the graph and get the minimal distance
|
v***a
发帖数: 365 | 6 Basic shortest distance problem. Can use BFS. |
a********m
发帖数: 15480 | |
m********l
发帖数: 4394 | 8 my explanation is that bad?
=======================
"Design a solution that finds the minimal distance to a shaded cell"
from where?
from every empty cells.
I put in those negative numbers. the negative numbers are the distances
=====================
-- what is shaded cells?
图中灰色的东西
=====================
【在 a********m 的大作中提到】
: 看不懂。
|
c****m
发帖数: 179 | 9 就是说，数字是weight，但是这个不是点对点的最短路径了，终点可以是任一个shade
里面的点。
给定起点的话，就是 run 一遍dijistra（shade之间的权值设为inf），然后扫一遍
shade的边上的点。 |
a********m
发帖数: 15480 | 10 这样的话跑一个dij就好了，碰到的第一个shade里面的返回就可以了吧。 |
|
|
o**********t
发帖数: 406 | 11 On this particular picture, the question is super easy.
Observe that the cells next to shaded ones are all -1, and one cell further
are all -2 ...so on.
Therefore, from any arbitrary cell, just always look for the cell that has
the smallest ABS value, and walk that direction.
【在 m********l 的大作中提到】
: 题目是：
: Provided with a grid with shaded cells.
: Design a solution that finds the minimal distance to a shaded cell
|
m********l
发帖数: 4394 | 12 Yup
But test yourself if you can do it during an interview.
There are at least 3 ways to solve this.
further
【在 o**********t 的大作中提到】
: On this particular picture, the question is super easy.
: Observe that the cells next to shaded ones are all -1, and one cell further
: are all -2 ...so on.
: Therefore, from any arbitrary cell, just always look for the cell that has
: the smallest ABS value, and walk that direction.
|
l*********y
发帖数: 370 | 13 int dx={1,1,0,-1,-1,-1,0,1}
int dy={-,1,1,1,0,0,-1,-1,-1}
#define N 100
#define INTMAX 0x7FFFFF
int opt[N][N]=INTMAX;
int fill_cell(int i,int j)
{
if(grid[i][j]=='shade')
{ opt[i][j]=0; return 0;}
if(opt[i][j]==INTMAX){
opt[i][j]=min_0<=k<8{fill_cell(i+dx[k],j+dy[k])+1 if valid(i+dx[k],j+
dy[k])}
}
return opt[i][j];
} |
z****u
发帖数: 104 | 14 are those numbers provided as known factor? Or provided by lz to illustrate
the problem?
further
【在 o**********t 的大作中提到】
: On this particular picture, the question is super easy.
: Observe that the cells next to shaded ones are all -1, and one cell further
: are all -2 ...so on.
: Therefore, from any arbitrary cell, just always look for the cell that has
: the smallest ABS value, and walk that direction.
|
m********l
发帖数: 4394 | 15 I provided them; hoped to make it easier to understand.
Apparently, it ended up confusing people more.
The interviewer said:
You have a grid with shaded cells.
Then, start from the top-right corner, you have -7 to a shaded cell, then -6
to a shaded cell, etc.
Design a solution that finds all the distances to a shaded cell.
illustrate
【在 z****u 的大作中提到】
: are those numbers provided as known factor? Or provided by lz to illustrate
: the problem?
:
: further
|
s*******n
发帖数: 499 | 16 这不就是个MDP么，学过AI的人都知道
-6
【在 m********l 的大作中提到】
: I provided them; hoped to make it easier to understand.
: Apparently, it ended up confusing people more.
: The interviewer said:
: You have a grid with shaded cells.
: Then, start from the top-right corner, you have -7 to a shaded cell, then -6
: to a shaded cell, etc.
: Design a solution that finds all the distances to a shaded cell.
:
: illustrate
|
l*********y
发帖数: 370 | 17 这个是图形学问题，阴影部分代表三维模型，将三维模型放在一个3维网格内，计算每一个网格里模型的最近距离。学过volumetric rendering都知道。 |
