c**z
发帖数: 669 | 1 其他都比较常规，有一道图的题目，一个 n*n 矩阵，每个房间可能是封闭的房间，可
能是警察，可能是开的房间，封闭的房间不能过，返回一个 n*n矩阵， 每一个元素是
最近的警察到这个房间的最短距离。
求问这题目怎么做 谢谢 |
T*****u
发帖数: 7103 | 2 解就是那个消防栓问题。从警察开始，n点的bfs吧。
【在 c**z 的大作中提到】
: 其他都比较常规，有一道图的题目，一个 n*n 矩阵，每个房间可能是封闭的房间，可
: 能是警察，可能是开的房间，封闭的房间不能过，返回一个 n*n矩阵， 每一个元素是
: 最近的警察到这个房间的最短距离。
: 求问这题目怎么做 谢谢
|
I**********n
发帖数: 77 | 3 DFS
--------
美国CS面试工作交流群QQ: 167615205
-------- |
v******l
发帖数: 60 | |
b*********t
发帖数: 170 | 5 多点BFS
【在 v******l 的大作中提到】
: BFS 吧？ 找最短的啊
|
c******3
发帖数: 296 | 6
从房间开始是不是更好？
【在 T*****u 的大作中提到】
: 解就是那个消防栓问题。从警察开始，n点的bfs吧。
|
r****7
发帖数: 2282 | 7 把警察都找出来，然后开始bfs
【在 c**z 的大作中提到】
: 其他都比较常规，有一道图的题目，一个 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 的大作中提到】
: 随便什么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 的大作中提到】
: 把警察都找出来，然后开始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 的大作中提到】
: 其他都比较常规，有一道图的题目，一个 n*n 矩阵，每个房间可能是封闭的房间，可
: 能是警察，可能是开的房间，封闭的房间不能过，返回一个 n*n矩阵， 每一个元素是
: 最近的警察到这个房间的最短距离。
: 求问这题目怎么做 谢谢
|
v******l
发帖数: 60 | |
b*********t
发帖数: 170 | 17 多点BFS
【在 v******l 的大作中提到】
: BFS 吧？ 找最短的啊
|
c******3
发帖数: 296 | 18
从房间开始是不是更好？
【在 T*****u 的大作中提到】
: 解就是那个消防栓问题。从警察开始，n点的bfs吧。
|
r****7
发帖数: 2282 | 19 把警察都找出来，然后开始bfs
【在 c**z 的大作中提到】
: 其他都比较常规，有一道图的题目，一个 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 的大作中提到】
: 随便什么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 的大作中提到】
: 把警察都找出来，然后开始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 的大作中提到】
: 看起来更像 Floyd-Warshall，如果警察多的话。
|
