2023-08-16:用go语言如何解决进击的骑士算法问题呢?

举报
福大大架构师每日一题 发表于 2023/08/16 17:26:21 2023/08/16
【摘要】 2023-08-16:用go写算法。一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上,你的 骑士 驻扎在坐标为 [0, 0] 的方格里。骑士的走法和中国象棋中的马相似,走 “日” 字:即先向左(或右)走 1 格,再向上(或下)走 2 格,或先向左(或右)走 2 格,再向上(或下)走 1 格,每次移动,他都可以像中国象棋中的马一样,选八个方向中的一个前进。返...

2023-08-16:用go写算法。一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上,

你的 骑士 驻扎在坐标为 [0, 0] 的方格里。

骑士的走法和中国象棋中的马相似,走 “日” 字:

即先向左(或右)走 1 格,再向上(或下)走 2 格,

或先向左(或右)走 2 格,再向上(或下)走 1 格,

每次移动,他都可以像中国象棋中的马一样,选八个方向中的一个前进。

返回 骑士前去征服坐标为 [x, y] 的部落所需的最小移动次数。

本题确保答案是一定存在的。

输入:x = 2, y = 1。

输出:1。

解释:[0, 0] → [2, 1]。

输入:x = 5, y = 5。

输出:4。

解释:[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]。

提示:|x| + |y| <= 300。

来自Indeed、谷歌、亚马逊、领英、英伟达。

来自左程云

答案2023-08-16:

大体步骤如下:

1.初始化一个二叉堆(binary heap)和一个哈希表(hashmap)用于存储已访问的位置。

2.将起始位置 [0, 0] 添加到二叉堆中,并初始化最小移动次数为无穷大。

3.进入循环,直到二叉堆为空:

  • 弹出堆顶位置,获取当前位置的代价、行号和列号。

  • 检查当前位置是否已经访问过,如果是则跳过该位置。

  • 检查当前位置是否达到目标位置,如果是则更新最小移动次数为当前代价,并结束循环。

  • 标记当前位置为已访问。

  • 尝试向八个方向移动,将可行的新位置添加到二叉堆中。

4.返回最小移动次数。

总的时间复杂度:在最坏情况下,需要访问所有格子,每次访问需要将新位置添加到二叉堆中,时间复杂度为O(N log N),其中N是需要访问的格子数量。

总的额外空间复杂度:使用了二叉堆和哈希表来存储已访问的位置,额外空间复杂度为O(N),其中N是需要访问的格子数量。

go完整代码如下:

package main

import (
	"fmt"
	"math"

	"github.com/emirpasic/gods/maps/hashmap"
	"github.com/emirpasic/gods/sets/hashset"
	"github.com/emirpasic/gods/trees/binaryheap"
)

// minKnightMoves calculates the minimum number of moves required for a knight to reach position (x, y).
func minKnightMoves(x, y int) int {
	heap := binaryheap.NewWith(func(a, b interface{}) int {
		return int(a.([]int)[0] + a.([]int)[1] - b.([]int)[0] - b.([]int)[1])
	})
	closed := hashmap.New()
	heap.Push([]int{0, distance(0, 0, x, y), 0, 0})
	ans := math.MaxInt32

	for heap.Size() > 0 {
		c, _ := heap.Pop()
		cur := c.([]int)
		cost := cur[0]
		row := cur[2]
		col := cur[3]

		if isClosed(closed, row, col) {
			continue
		}

		if row == x && col == y {
			ans = cost
			break
		}

		close(closed, row, col)
		add(cost+1, row+2, col+1, x, y, closed, heap)
		add(cost+1, row+1, col+2, x, y, closed, heap)
		add(cost+1, row-1, col+2, x, y, closed, heap)
		add(cost+1, row-2, col+1, x, y, closed, heap)
		add(cost+1, row-2, col-1, x, y, closed, heap)
		add(cost+1, row-1, col-2, x, y, closed, heap)
		add(cost+1, row+1, col-2, x, y, closed, heap)
		add(cost+1, row+2, col-1, x, y, closed, heap)
	}

	return ans
}

// isClosed checks if the position (r, c) has been visited before.
func isClosed(closed *hashmap.Map, r, c int) bool {
	set, found := closed.Get(r)
	if !found {
		return false
	}
	return set.(*hashset.Set).Contains(c)
}

// close adds the position (r, c) to the closed set.
func close(closed *hashmap.Map, r, c int) {
	set, found := closed.Get(r)
	if !found {
		set = hashset.New()
		closed.Put(r, set)
	}
	set.(*hashset.Set).Add(c)
}

// add adds the position (r, c) to the heap if it hasn't been visited before.
func add(cost, r, c, x, y int, closed *hashmap.Map, heap *binaryheap.Heap) {
	if !isClosed(closed, r, c) {
		heap.Push([]int{cost, distance(r, c, x, y), r, c})
	}
}

// distance calculates the Manhattan distance divided by 3.
// This is used as the heuristic function for estimating the cost.
func distance(r, c, x, y int) int {
	return (int(math.Abs(float64(x-r))) + int(math.Abs(float64(y-c)))) / 3
}

func main() {
	x, y := 2, 1
	result := minKnightMoves(x, y)
	fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下:

use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};

#[derive(Copy, Clone, Eq, PartialEq)]
struct KnightMove {
    cost: i32,
    distance: i32,
    row: i32,
    col: i32,
}

impl Ord for KnightMove {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.cost + self.distance)
            .cmp(&(other.cost + other.distance))
            .reverse()
    }
}

impl PartialOrd for KnightMove {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn min_knight_moves(x: i32, y: i32) -> i32 {
    let mut heap = BinaryHeap::new();
    let mut closed: HashMap<i32, HashMap<i32, bool>> = HashMap::new();
    heap.push(KnightMove {
        cost: 0,
        distance: distance(0, 0, x, y),
        row: 0,
        col: 0,
    });
    let mut ans = i32::MAX;

    while let Some(cur) = heap.pop() {
        let cost = cur.cost;
        let row = cur.row;
        let col = cur.col;

        if is_popped(&closed, row, col) {
            continue;
        }

        if row == x && col == y {
            ans = cost;
            break;
        }

        close(&mut closed, row, col);
        add(cost + 1, row + 2, col + 1, x, y, &mut closed, &mut heap);
        add(cost + 1, row + 1, col + 2, x, y, &mut closed, &mut heap);
        add(cost + 1, row - 1, col + 2, x, y, &mut closed, &mut heap);
        add(cost + 1, row - 2, col + 1, x, y, &mut closed, &mut heap);
        add(cost + 1, row - 2, col - 1, x, y, &mut closed, &mut heap);
        add(cost + 1, row - 1, col - 2, x, y, &mut closed, &mut heap);
        add(cost + 1, row + 1, col - 2, x, y, &mut closed, &mut heap);
        add(cost + 1, row + 2, col - 1, x, y, &mut closed, &mut heap);
    }

    ans
}

fn is_popped(closed: &HashMap<i32, HashMap<i32, bool>>, r: i32, c: i32) -> bool {
    if let Some(cols) = closed.get(&r) {
        if let Some(&popped) = cols.get(&c) {
            return popped;
        }
    }
    false
}

fn close(closed: &mut HashMap<i32, HashMap<i32, bool>>, r: i32, c: i32) {
    let cols = closed.entry(r).or_default();
    cols.insert(c, true);
}

fn add(
    cost: i32,
    r: i32,
    c: i32,
    x: i32,
    y: i32,
    closed: &mut HashMap<i32, HashMap<i32, bool>>,
    heap: &mut BinaryHeap<KnightMove>,
) {
    if !is_popped(closed, r, c) {
        heap.push(KnightMove {
            cost,
            distance: distance(r, c, x, y),
            row: r,
            col: c,
        });
    }
}

fn distance(r: i32, c: i32, x: i32, y: i32) -> i32 {
    (i32::abs(x - r) + i32::abs(y - c)) / 3
}

fn main() {
    let x = 2;
    let y = 1;
    let result = min_knight_moves(x, y);
    println!("Minimum knight moves: {}", result);
}

在这里插入图片描述

c++完整代码如下:

#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

bool isPoped(unordered_map<int, unordered_set<int>>& closed, int r, int c) {
    return closed.count(r) && closed[r].count(c);
}

void close(unordered_map<int, unordered_set<int>>& closed, int r, int c) {
    if (!closed.count(r)) {
        closed[r] = unordered_set<int>();
    }
    closed[r].insert(c);
}

int distance(int r, int c, int x, int y);

void add(int cost, int r, int c, int x, int y, unordered_map<int, unordered_set<int>>& closed,
    priority_queue<vector<int>, vector<vector<int>>, greater<>>& heap) {
    if (!isPoped(closed, r, c)) {
        heap.push({ cost, distance(r, c, x, y), r, c });
    }
}

int distance(int r, int c, int x, int y) {
    return (abs(x - r) + abs(y - c)) / 3;
}

int minKnightMoves(int x, int y) {
    priority_queue<vector<int>, vector<vector<int>>, greater<>> heap;
    unordered_map<int, unordered_set<int>> closed;
    heap.push({ 0, distance(0, 0, x, y), 0, 0 });
    int ans = INT_MAX;
    while (!heap.empty()) {
        vector<int> cur = heap.top();
        heap.pop();
        int cost = cur[0];
        int row = cur[2];
        int col = cur[3];
        if (isPoped(closed, row, col)) {
            continue;
        }
        if (row == x && col == y) {
            ans = cost;
            break;
        }
        close(closed, row, col);
        add(cost + 1, row + 2, col + 1, x, y, closed, heap);
        add(cost + 1, row + 1, col + 2, x, y, closed, heap);
        add(cost + 1, row - 1, col + 2, x, y, closed, heap);
        add(cost + 1, row - 2, col + 1, x, y, closed, heap);
        add(cost + 1, row - 2, col - 1, x, y, closed, heap);
        add(cost + 1, row - 1, col - 2, x, y, closed, heap);
        add(cost + 1, row + 1, col - 2, x, y, closed, heap);
        add(cost + 1, row + 2, col - 1, x, y, closed, heap);
    }
    return ans;
}

int main() {
    int x = 2;
    int y = 1;
    int result = minKnightMoves(x, y);
    cout << "Minimum number of knight moves: " << result << endl;
    return 0;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。