题目：为高尔夫比赛砍树
•0表示障碍，无法触碰
•1表示地面，可以行走
•比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为1（即变为地面）。
你将从(0, 0)点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回-1。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
示例 1：
输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
c罗开什么车示例 2：唐山车市
输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。示例 3：
输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。
提示：
•m == forest.length
•n == forest[i].length
• 1 <= m, n <= 50
•0 <= forest[i][j] <= 109
语言:Python
class Solution(object):
def cutOffTree(self, forest):畅网查询
trees = sorted((v, r, c) for r, row in enumerate(forest)
for c, v in enumerate(row) if v >1)
sr = sc = ans =0
for _, tr, tc in trees:
d = dist(forest, sr, sc, tr, tc)
if d <0: return-1
ans += d
sr, sc = tr, tc
return ans
语言:Python
def bfs(forest, sr, sc, tr, tc):
R, C = len(forest), len(forest[0])
抓拍queue = collections.deque([(sr, sc, 0)])
seen = {(sr, sc)}
while queue:
r, c, d = queue.popleft()
if r == tr and c == tc:
return d
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if (0<= nr < R and0<= nc < C and
(nr, nc) not in seen and forest[nr][nc]):
seen.add((nr, nc))
queue.append((nr, nc, d+1))
return-1
语言:Python
def astar(forest, sr, sc, tr, tc):
R, C = len(forest), len(forest[0])
heap = [(0, 0, sr, sc)]
cost = {(sr, sc): 0}
while heap:
f, g, r, c = heapq.heappop(heap)
if r == tr and c == tc: return g
for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
if0<= nr < R and0<= nc < C and forest[nr][nc]:
ncost = g +1+ abs(nr - tr) + abs(nc - tc)
if ncost < ((nr, nc), 9999):
cost[nr, nc] = ncost
heapq.heappush(heap, (ncost, g+1, nr, nc))
return-1
铁骆驼修复语言:Java
class Solution {
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList();
for (int r = 0; r < forest.size(); ++r) {
for (int c = 0; c < (0).size(); ++c) {
int v = (r).get(c);
if (v > 1) trees.add(new int[]{v, r, c});
}
}
Collections.sort(trees, (a, b) -> Integerpare(a[0], b[0]));
int ans = 0, sr = 0, sc = 0;
for (int[] tree: trees) {
int d = dist(forest, sr, sc, tree[1], tree[2]);
if (d < 0) return -1;
ans += d;
sr = tree[1]; sc = tree[2];
}
return ans;
}
}
语言:Java
public int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
int R = forest.size(), C = (0).size();
Queue<int[]> queue = new LinkedList();
queue.add(new int[]{sr, sc, 0});
boolean[][] seen = new boolean[R][C];
seen[sr][sc] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == tr && cur[1] == tc) return cur[2];
for (int di = 0; di < 4; ++di) {
int r = cur[0] + dr[di];
int c = cur[1] + dc[di];
if (0 <= r && r < R && 0 <= c && c < C &&
!seen[r][c] && (r).get(c) > 0) {
seen[r][c] = true;
queue.add(new int[]{r, c, cur[2]+1});
}
}
}
return -1;
}
语言:Java
public int cutOffTree(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
int R = forest.size(), C = (0).size();
PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
(a, b) -> Integerpare(a[0], b[0]));
heap.offer(new int[]{0, 0, sr, sc});
HashMap<Integer, Integer> cost = new HashMap();
cost.put(sr * C + sc, 0);
while (!heap.isEmpty()) {
int[] cur = heap.poll();
int g = cur[1], r = cur[2], c = cur[3];
if (r == tr && c == tc) return g;
for (int di = 0; di < 4; ++di) {
int nr = r + dr[di], nc = c + dc[di];
if (0 <= nr && nr < R && 0 <= nc && nc < C && (nr).get(nc) > 0) {
int ncost = g + 1 + Math.abs(nr-tr) + Math.abs(nc-tr);
if (ncost < OrDefault(nr * C + nc, 9999)) {
cost.put(nr * C + nc, ncost);
heap.offer(new int[]{ncost, g+1, nr, nc});
}
}
}
}
return -1;
}
语言:cpp
/***************************************************
Author: hqztrue
Complexity: O(n^3)
If you find this solution helpful, plz give a star:)
***************************************************/
const int N=55,inf=~0u>>2;
struct query{
int x1,x2,y1,y2,d;
query(int _x1=0,int _x2=0,int _y1=0,int _y2=0):x1(_x1),x2(_x2),y1(_y1),y2(_y2){d=inf;} }Q[N*N];
int d[N][N],qx[N*N],qy[N*N],Q1;
vector<vector<int>> A;
void SSSP(int x1,int x2,int y1,int y2,int sx,int sy){
for (int i=x1;i<=x2;++i)
for (int j=y1;j<=y2;++j)d[i][j]=inf;
d[sx][sy]=0; qx[0]=sx; qy[0]=sy;
int h=0,t=1;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
while (h<t){
int x=qx[h],y=qy[h++],_d=d[x][y];
for (int i=0;i<4;++i){
int _x=x+dx[i],_y=y+dy[i];
if (_x<x1||_x>x2||_y<y1||_y>y2)continue;
if (A[_x][_y]&&d[_x][_y]==inf)d[_x][_y]=_d+1,qx[t]=_x,qy[t++]=_y;
}
}
}
void shortest_path(int x1,int x2,int y1,int y2,const vector<query*> &q){
if (!q.size())return;
vector<query*> q1,q2;
if (x2-x1<=y2-y1){
int mid=(y1+y2)/2;
for (int i=x1;i<=x2;++i){
if (!A[i][mid])continue;
SSSP(x1,x2,y1,y2,i,mid);
for (int j=0;j<q.size();++j){
query *p=q[j]; p->d=min(p->d,d[p->x1][p->y1]+d[p->x2][p->y2]);
}
}
for (int i=0;i<q.size();++i){
if (q[i]->y1<mid&&q[i]->y2<mid)q1.push_back(q[i]);
else if (q[i]->y1>mid&&q[i]->y2>mid)q2.push_back(q[i]);
}
shortest_path(x1,x2,y1,mid-1,q1);
mustang mach-eshortest_path(x1,x2,mid+1,y2,q2);
发布评论