9.11京东java工程师笔试

/*
*键盘输入
时间限制： 3000MS
内存限制： 589824KB
题目描述：
你在使用一个特殊的键盘输入一个字符串。键盘是一个矩形网格的形状，有各种不同的排列，每个按键上的字符互不相同，最多有 94 个按键（除空格外共有 94 个可见 ASCII 字符，ASCII 码为 33~126）。你需要操作一个机械手来点击这个键盘，机械手可以上下左右移动，每移动一格耗时 x，移动过程中（不包括一开始或者点击前后）转向耗时 y，每次点击键盘耗时 z。一开始，机械手位于左上角。请计算打完这个字符串最少需要多少时间。



输入描述
第一行五个空格隔开的整数 n, m, x, y, z，0 < n * m <= 94，1 <= x, y, z <= 100000

后面 n 行，每行一个由 m 个字符组成的字符串，表示键盘的配列，保证 m 个字符都是 ASCII 可见字符，不是空格且互不相同。

最后一行一个由上述配列中存在的字符组成的字符串，长度不超过 100000。

输出描述
一个整数，表示最少需要的时间


样例输入
2 2 1 1 1
.E
:F
EE:F.:
样例输出
15

提示
步骤拆解

E→2   EE→3   EE: →7（移动中涉及了转向）   EE:F→9   EE:F.→13（移动中涉及了转向）   EE:F.:→15
*/
package main

import (
	"fmt"
	"strings"
)

type Pos struct {
	X, Y int
}

func main() {
	var n, m, x, y, z int
	fmt.Scan(&n, &m, &x, &y, &z)
	// fmt.Println(n, m, x, y, z)

	array := make([][]string, n)
	posMap := make(map[string]Pos)
	for i := 0; i < n; i++ {
		var temp string
		fmt.Scan(&temp)
		js := strings.Split(temp, "")
		array[i] = make([]string, m)
		for j := 0; j < m; j++ {

			array[i][j] = js[j]
			posMap[js[j]] = Pos{i, j}
		}
	}

	// fmt.Println(array, posMap)

	var tempX, tempY int
	var final string
	var res int
	fmt.Scan(&final)
	for _, s := range strings.Split(final, "") {
		target := posMap[s]
		var temp int
		temp += abs(target.X, tempX) * x
		temp += abs(target.Y, tempY) * x
		// 需要转向
		if (target.X != tempX) && (target.Y != tempY) {
			temp += y
		}
		// 敲击一下
		temp += z
		res += temp
		// fmt.Println("target", target, "tempCost", temp)

		tempX, tempY = target.X, target.Y
	}

	fmt.Println(res)

}

func abs(x, y int) int {

	temp := x - y
	if temp < 0 {
		return (-1) * temp
	}

	return temp
}

/*
* 题目描述
Systemd 依赖
时间限制： 3000MS
内存限制： 589824KB
题目描述：

       你可能不喜欢 systemd，但很可能每天都要面对它——Linux 下广泛使用的 init 程序。

       在一个 systemd units 中，可以使用 Requires=… 的语法来引入依赖，当服务 a 引入了服务 b 作为依赖之后，服务 a 启动时 b 会随之启动，b 停止时 a 会随之停止。本题会给你 n 个服务和它们之间的依赖关系，一开始所有服务都处于停止状态，然后进行若干次启动和停止操作，你需要在每一次操作后输出当前正在运行的服务数量。假设所有服务都能稳定运行、正常启动和退出。为了简化输入，所有服务名使用序号（1~n）代替。可以启动正在运行的程序，也可以停止已经停止的程序，这样的操作将不会造成任何变化。



输入描述
第一行两个空格隔开的整数 n, q，表示服务的数量和询问的数量，1 <= n, q <= 500。

下面 n 行，其中的第 i 行第一个整数 c 表示第 i 个服务所依赖的服务数量，后面 c 个整数表示它所依赖的各个服务，保证这 c 个整数在 1~n 范围内，互不相等且都不等于 i。

下面 q 行，每行两个空格隔开的整数 x, y。x 为 1 或 0，1 表示启动服务，0 表示停止服务。y 表示启动或停止的服务的序号。

输出描述
q 行，每行一个整数，表示每次操作后这 n 个服务中正在运行的服务数量。


样例输入
3 2
1 2
1 3
0
1 1
0 2
样例输出
3
1
*/
package main

import (
	"fmt"
)

func main() {
	var n, q int
	fmt.Scan(&n)
	fmt.Scan(&q)

	// fmt.Println(n, q)

	// key 依赖的value
	depend := make(map[int][]int)
	// key为被依赖的
	dependReverse := make(map[int][]int)
	// key标识服务 value标识是否启动
	service := make(map[int]bool)
	for i := 1; i <= n; i++ {
		//service[i]=false
		if len(depend[i]) < 1 {
			depend[i] = make([]int, 0)
		}
		var total int
		fmt.Scan(&total)
		for ii := 1; ii <= total; ii++ {
			var d int
			fmt.Scan(&d)
			depend[i] = append(depend[i], d)
			if len(dependReverse[d]) < 1 {
				dependReverse[d] = make([]int, 0)
			}
			dependReverse[d] = append(dependReverse[d], i)
		}

	}
	// fmt.Println(depend)
	// fmt.Println(dependReverse)

	for i := 1; i <= q; i++ {
		var enable, idx int
		fmt.Scan(&enable)
		fmt.Scan(&idx)
		idxs := []int{idx}
		if enable == 1 {
			// 启动所有依赖项
			for {
				if len(idxs) < 1 {
					break
				}
				anothers := make([]int, 0)
				for _, iidx := range idxs {
					service[iidx] = true
					// 依赖的下游也都启动起来
					for _, ii := range depend[iidx] {
						if service[ii] {
							continue
						}
						service[ii] = true
						anothers = append(anothers, ii)
					}
				}
				idxs = anothers

			}

		} else {
			// 停用被依赖项
			for {
				if len(idxs) < 1 {
					break
				}
				anothers := make([]int, 0)
				for _, iidx := range idxs {
					if _, ok := service[iidx]; ok {
						delete(service, iidx)
					}
					for _, ii := range dependReverse[iidx] {
						if _, ok := service[ii]; !ok {
							continue
						}
						delete(service, ii)
						anothers = append(anothers, ii)
					}
				}
				idxs = anothers

			}
		}
		// fmt.Println(service)
		fmt.Println(len(service))
	}

}