f**********e
发帖数: 288 | 1 给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要
求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.
唉， 不会做哦。。 | k****r
发帖数: 807 | 2 需要测试每个可以放新器材的点，从每个这样的点bfs向外拓展，用queue哦，queue里
面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
的时候，stop，记住一共走了多少。
每个点都测，找最好的。
这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。 | w*****1
发帖数: 6807 | 3 方便的话能给个代码么
【在 k****r 的大作中提到】
: 需要测试每个可以放新器材的点，从每个这样的点bfs向外拓展，用queue哦，queue里
: 面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
: 的时候，stop，记住一共走了多少。
: 每个点都测，找最好的。
: 这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。
| k****r
发帖数: 807 | 4 public static Point minDistanceInMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int res = Integer.MAX_VALUE;
int numOfOne = countOne(matrix);
Point minP = new Point(-1,-1,-1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
int newRes = goHelper(matrix, i, j, res, numOfOne);
if ( newRes < res) {
minP.x = i;
minP.y = j;
res = newRes;
}
}
}
}
return minP;
}
public static int countOne(int[][] matrix) {
int res = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1) res++;
}
}
return res;
}
public static int goHelper(int[][] matrix, int x, int y, int curr, int
numOfOne) {
Queue q = new LinkedList<>();
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
visited[x][y] = true;
q.add(new Point(x,y,0));
int count = 0;
int step = 0;
while (!q.isEmpty()) {
Point p = q.poll();
int[][] directions = {{0,1},{1,0},{-1,0},{0,-1}};
for (int[] d : directions) {
int nx = p.x + d[0];
int ny = p.y + d[1];
int nd = p.d + 1;
if (nx < 0 || nx >= matrix.length
|| ny < 0 || ny >= matrix[0].length
|| matrix[nx][ny] == -1 || visited[nx][ny] == true)
continue;
visited[nx][ny] = true;
if (matrix[nx][ny] == 0) {
q.add(new Point(nx,ny,nd));
}
if (matrix[nx][ny] == 1) {
step += nd;
count++;
if (count == numOfOne) {
return step;
}
}
}
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[][] input = {{0, 0, 0, -1, 0},{0, 1, 0, 0, 1},{0, -1, 1, 0, 0
}};
Point p = minDistanceInMatrix(input);
System.out.println(p.x +","+p.y);
}
【在 w*****1 的大作中提到】
: 方便的话能给个代码么
| a***u
发帖数: 383 | 5 我觉得应该对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
最后O（n^2）一遍找最小值。
复杂度O（e*n^2）
如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。 | k****r
发帖数: 807 | 6 看你设备多还是空地多吧，而且，每个设备都bfs，必须覆盖整个matrix，从空地出发
不一定需要。
【在 a***u 的大作中提到】
: 我觉得应该对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
: 最后O（n^2）一遍找最小值。
: 复杂度O（e*n^2）
: 如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。
| f**********e
发帖数: 288 | | f********y
发帖数: 156 | 8 貌似可以这样：
每个点用一个e 位的 bitmap.
从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
1；第一个全是1的点就是离大家最近的点 | s****3
发帖数: 270 | 9 bitmap 用得好!!!but同时做用比较多memory ? 分开做比较省memory but time
complexity is the same.
【在 f********y 的大作中提到】
: 貌似可以这样：
: 每个点用一个e 位的 bitmap.
: 从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
: 1；第一个全是1的点就是离大家最近的点
| p*********g
发帖数: 26 | 10 请问两个器材的距离定义？假设为|x0-x1|+|y0-y1|
1. 两个array，cntn[n], cntm[m], 把所有e个器材过一遍，之后cntn[i]记录所有在
col[i]的器材个数，cntm类似，O(e)。在此两个数组上计算lsum, lsum[i]为所有横坐
标<=i的器材个数，类似的再计算rsum, upsum和downsum.O(n+m)
2. 取第一个没有器材的点，比如m[i][j]，计算从该点到所有e个器材的距离之和 - O(
e)
3. 然后遍历所有没有器材的点，从左向右从上到下;向右遍历时之前的距离和dsum减去
所有位于右侧的器材个数(rsum[i] - cntn[i])*1，加上左侧和当前列的器材个数(lsum
[i])*1；由上至下类似。O(n*m)
返回#3中最小值。
各位大神走过路过还请轻拍
【在 f**********e 的大作中提到】
: 给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要
: 求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.
: 唉， 不会做哦。。
| h**p
发帖数: 211 | 11 这种做法对没用障碍物的题是可行的，但是lz给的题是包含障碍，你的算法不行
最快的应该只能是O(e * m * n)了
O(
lsum
【在 p*********g 的大作中提到】
: 请问两个器材的距离定义？假设为|x0-x1|+|y0-y1|
: 1. 两个array，cntn[n], cntm[m], 把所有e个器材过一遍，之后cntn[i]记录所有在
: col[i]的器材个数，cntm类似，O(e)。在此两个数组上计算lsum, lsum[i]为所有横坐
: 标<=i的器材个数，类似的再计算rsum, upsum和downsum.O(n+m)
: 2. 取第一个没有器材的点，比如m[i][j]，计算从该点到所有e个器材的距离之和 - O(
: e)
: 3. 然后遍历所有没有器材的点，从左向右从上到下;向右遍历时之前的距离和dsum减去
: 所有位于右侧的器材个数(rsum[i] - cntn[i])*1，加上左侧和当前列的器材个数(lsum
: [i])*1；由上至下类似。O(n*m)
: 返回#3中最小值。
| f**********e
发帖数: 288 | 12 求贴code， 大牛。。
【在 h**p 的大作中提到】
: 这种做法对没用障碍物的题是可行的，但是lz给的题是包含障碍，你的算法不行
: 最快的应该只能是O(e * m * n)了
:
: O(
: lsum
|
|
