c**z 发帖数: 669 | 1 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可
能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是
最近的警察到这个房间的最短距离。
求问这题目怎么做 谢谢 |
T*****u 发帖数: 7103 | 2 解就是那个消防栓问题。从警察开始,n点的bfs吧。
【在 c**z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可 : 能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是 : 最近的警察到这个房间的最短距离。 : 求问这题目怎么做 谢谢
|
I**********n 发帖数: 77 | 3 DFS
--------
美国CS面试工作交流群QQ: 167615205
-------- |
v******l 发帖数: 60 | |
b*********t 发帖数: 170 | 5 多点BFS
【在 v******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BFS 吧? 找最短的啊
|
c******3 发帖数: 296 | 6
从房间开始是不是更好?
【在 T*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 解就是那个消防栓问题。从警察开始,n点的bfs吧。
|
r****7 发帖数: 2282 | 7 把警察都找出来,然后开始bfs
【在 c**z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可 : 能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是 : 最近的警察到这个房间的最短距离。 : 求问这题目怎么做 谢谢
|
l****o 发帖数: 315 | 8 随便什么fs,反正如果值比当前格的小就override咯。没区别。 |
y**********a 发帖数: 824 | 9 看起来更像 Floyd-Warshall,如果警察多的话。 |
y**********a 发帖数: 824 | 10 看起来更像 Floyd-Warshall,如果警察多的话。 |
|
|
r****7 发帖数: 2282 | 11 are you sure?
【在 l****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 随便什么fs,反正如果值比当前格的小就override咯。没区别。
|
b********r 发帖数: 620 | 12 this one seems best. starting from police and override the distance with
smaller value if multiple polices can reach the same office
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把警察都找出来,然后开始bfs
|
a*******a 发帖数: 66 | 13 对每一个位置做recursion,过程中保存已找到的结果;recursion的end case是警察周
围的房间(距离=1) |
c**z 发帖数: 669 | 14 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可
能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是
最近的警察到这个房间的最短距离。
求问这题目怎么做 谢谢 |
T*****u 发帖数: 7103 | 15 解就是那个消防栓问题。从警察开始,n点的bfs吧。
【在 c**z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可 : 能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是 : 最近的警察到这个房间的最短距离。 : 求问这题目怎么做 谢谢
|
v******l 发帖数: 60 | |
b*********t 发帖数: 170 | 17 多点BFS
【在 v******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BFS 吧? 找最短的啊
|
c******3 发帖数: 296 | 18
从房间开始是不是更好?
【在 T*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 解就是那个消防栓问题。从警察开始,n点的bfs吧。
|
r****7 发帖数: 2282 | 19 把警察都找出来,然后开始bfs
【在 c**z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其他都比较常规,有一道图的题目,一个 n*n 矩阵,每个房间可能是封闭的房间,可 : 能是警察,可能是开的房间,封闭的房间不能过,返回一个 n*n矩阵, 每一个元素是 : 最近的警察到这个房间的最短距离。 : 求问这题目怎么做 谢谢
|
l****o 发帖数: 315 | 20 随便什么fs,反正如果值比当前格的小就override咯。没区别。 |
|
|
y**********a 发帖数: 824 | 21 看起来更像 Floyd-Warshall,如果警察多的话。 |
y**********a 发帖数: 824 | 22 看起来更像 Floyd-Warshall,如果警察多的话。 |
r****7 发帖数: 2282 | 23 are you sure?
【在 l****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 随便什么fs,反正如果值比当前格的小就override咯。没区别。
|
b********r 发帖数: 620 | 24 this one seems best. starting from police and override the distance with
smaller value if multiple polices can reach the same office
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把警察都找出来,然后开始bfs
|
a*******a 发帖数: 66 | 25 对每一个位置做recursion,过程中保存已找到的结果;recursion的end case是警察周
围的房间(距离=1) |
f**********t 发帖数: 1001 | 26 void DistanceAround(const vector &rooms, vector> &res,
int i, int k) {
const static int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
res[i][k] = 0;
queue> qu;
qu.push(make_pair(i, k));
while(!qu.empty()) {
int x = qu.front().first;
int y = qu.front().second;
qu.pop();
for (int z = 0; z < 4; ++z) {
int xx = x + directions[z][0];
int yy = y + directions[z][1];
if (0 <= xx && xx < (int)rooms.size()
&& 0 <= yy && yy < (int)rooms[0].size()
&& rooms[xx][yy] != 'b' && res[x][y] + 1 < res[xx][yy]) {
res[xx][yy] = res[x][y] + 1;
qu.push(make_pair(xx, yy));
}
}
}
}
vector> PliceDistance(const vector &rooms) {
vector> res;
if (rooms.empty() || rooms[0].empty()) {
return res;
}
int row = rooms.size();
int col = rooms[0].size();
for (int i = 0; i < row; ++i) {
res.emplace_back(col, INT_MAX);
}
for (int i = 0; i < row; ++i) {
for (int k = 0; k < col; ++k) {
if (rooms[i][k] == 'p') {
DistanceAround(rooms, res, i, k);
}
}
}
return res;
} |
g****s 发帖数: 340 | 27 这个对。
【在 y**********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看起来更像 Floyd-Warshall,如果警察多的话。
|