谁知道那家时尚以透视装风格为主？# Fashion - 美丽时尚
f*e
1 楼
给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要
求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.
唉， 不会做哦。。
求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.
唉， 不会做哦。。
x*c
2 楼
最近狂草透视装，就是那种纱纱的衫衫，有谁知道那家时尚以这种风格为主？
k*r
3 楼
需要测试每个可以放新器材的点，从每个这样的点bfs向外拓展，用queue哦，queue里
面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
的时候，stop，记住一共走了多少。
每个点都测，找最好的。
这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。
面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
的时候，stop，记住一共走了多少。
每个点都测，找最好的。
这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。
x*c
4 楼
re
【在 x**c 的大作中提到】
: 最近狂草透视装，就是那种纱纱的衫衫，有谁知道那家时尚以这种风格为主？
【在 x**c 的大作中提到】
: 最近狂草透视装，就是那种纱纱的衫衫，有谁知道那家时尚以这种风格为主？
w*1
5 楼
方便的话能给个代码么
【在 k****r 的大作中提到】
: 需要测试每个可以放新器材的点，从每个这样的点bfs向外拓展，用queue哦，queue里
: 面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
: 的时候，stop，记住一共走了多少。
: 每个点都测，找最好的。
: 这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。
【在 k****r 的大作中提到】
: 需要测试每个可以放新器材的点，从每个这样的点bfs向外拓展，用queue哦，queue里
: 面存的是point已经对应已经走的length，墙不能走，空的能走，visited了所有的器材
: 的时候，stop，记住一共走了多少。
: 每个点都测，找最好的。
: 这是我目前知道的最好的方法了，如果有真牛知道更好的，还请指粗。
A*6
6 楼
顶。。。。。。。。。。。。。
k*r
7 楼
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 的大作中提到】
: 方便的话能给个代码么
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
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
8 楼
我觉得应该对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
最后O（n^2）一遍找最小值。
复杂度O（e*n^2）
如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。
最后O（n^2）一遍找最小值。
复杂度O（e*n^2）
如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。
k*r
9 楼
看你设备多还是空地多吧，而且，每个设备都bfs，必须覆盖整个matrix，从空地出发
不一定需要。
【在 a***u 的大作中提到】
: 我觉得应该对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
: 最后O（n^2）一遍找最小值。
: 复杂度O（e*n^2）
: 如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。
不一定需要。
【在 a***u 的大作中提到】
: 我觉得应该对 e个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
: 最后O（n^2）一遍找最小值。
: 复杂度O（e*n^2）
: 如果是对每个可放新设备点bfs，复杂度是O(n^4)吧。
f*e
10 楼
多谢， 代码又点长啊。。：－）
f*y
11 楼
貌似可以这样：
每个点用一个e 位的 bitmap.
从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
1；第一个全是1的点就是离大家最近的点
每个点用一个e 位的 bitmap.
从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
1；第一个全是1的点就是离大家最近的点
s*3
12 楼
bitmap 用得好!!!but同时做用比较多memory ? 分开做比较省memory but time
complexity is the same.
【在 f********y 的大作中提到】
: 貌似可以这样：
: 每个点用一个e 位的 bitmap.
: 从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
: 1；第一个全是1的点就是离大家最近的点
complexity is the same.
【在 f********y 的大作中提到】
: 貌似可以这样：
: 每个点用一个e 位的 bitmap.
: 从e个点同时开始BFS, 就是向四周染色，染色就是把那个点相应的bitmap中的bit 设为
: 1；第一个全是1的点就是离大家最近的点
p*g
13 楼
请问两个器材的距离定义？假设为|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.
: 唉， 不会做哦。。
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
14 楼
这种做法对没用障碍物的题是可行的，但是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中最小值。
最快的应该只能是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
15 楼
求贴code， 大牛。。
【在 h**p 的大作中提到】
: 这种做法对没用障碍物的题是可行的，但是lz给的题是包含障碍，你的算法不行
: 最快的应该只能是O(e * m * n)了
:
: O(
: lsum
【在 h**p 的大作中提到】
: 这种做法对没用障碍物的题是可行的，但是lz给的题是包含障碍，你的算法不行
: 最快的应该只能是O(e * m * n)了
:
: O(
: lsum
相关阅读
[参加活动] 。步步生莲。三双普通凉鞋美女老了什么样 (转载)国内crocs鞋这么贵？499元！ (转载)这周coach outlet还有extra 30%off吗？请教crabtree的护手霜[参加活动]刚跑完步奔我的大黄蜂跑鞋丝袜破了不要紧吗？参加婚礼穿什么sartoREAList问个问题：男装鞋子JOHNSTON & MURPHY类似价位/质量的还有其他什么牌子？求 正价店 COACH的Coupon，价格请站内短信联系，谢谢！KATE SPADE 25% CODEamazon 上美丽日记降到11多块钱了到了中年才（还没）悟出来：人生就是挖鼻屎，看浮云！ (转载)今年要有一双防水台的高跟鞋－from ELLEDinoDirect 怎么免运费呀？谢谢！请问在北美怎么购买日系护肤呢？GG一名，趁着深夜闪奔一次[参加活动] 奔新买的鞋说个笑话： 最近天天早晨去游泳， 遇到大陆来的家庭主妇 (转载)我买了几件forever21的衣服