https://leetcode.com/problems/snake-in-matrix/

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并遵循一系列命令移动。

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

示例 1：

输入：n = 2, commands = ["RIGHT","DOWN"]
输出：3

A: 贪吃蛇

impl Solution {
    pub fn final_position_of_snake(n: i32, commands: Vec<String>) -> i32 {
        // Initialize the snake's position
        let mut row = 0;
        let mut col = 0;

        // Define the movement directions
        let directions: std::collections::HashMap<&str, (i32, i32)> = [
            ("UP", (-1, 0)),
            ("RIGHT", (0, 1)),
            ("DOWN", (1, 0)),
            ("LEFT", (0, -1))
        ].iter().cloned().collect();

        // Execute each command
        for command in commands {
            // Get the direction of movement
            let (dr, dc) = directions.get(command.as_str()).unwrap();

            // Update the snake's position
            row += dr;
            col += dc;

            // Ensure the snake stays within the grid boundaries
            row = row.max(0).min(n - 1);
            col = col.max(0).min(n - 1);
        }

        // Calculate the final position
        (row * n) + col
    }
}

B.

use std::collections::HashMap;
impl Solution {
    pub fn count_good_nodes(edges: Vec<Vec<i32>>) -> i32 {
        // Build the adjacency list
        let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
        for edge in &edges {
            graph.entry(edge[0]).or_insert(Vec::new()).push(edge[1]);
            graph.entry(edge[1]).or_insert(Vec::new()).push(edge[0]);
        }

        let mut good_nodes = 0;

        fn dfs(node: i32, parent: i32, graph: &HashMap<i32, Vec<i32>>, good_nodes: &mut i32) -> i32 {
            let mut subtree_sizes = Vec::new();

            if let Some(children) = graph.get(&node) {
                for &child in children {
                    if child != parent {
                        let subtree_size = dfs(child, node, graph, good_nodes);
                        subtree_sizes.push(subtree_size);
                    }
                }
            }

            // If it's a leaf node or all subtrees have the same size
            if subtree_sizes.is_empty() || subtree_sizes.iter().all(|&size| size == subtree_sizes[0]) {
                *good_nodes += 1;
            }

            // Return the size of this subtree
            1 + subtree_sizes.iter().sum::<i32>()
        }

        dfs(0, -1, &graph, &mut good_nodes);
        good_nodes
    }
}

C. 等下写