题面描述

塔子哥在一个 $m \times n$ 的崎岖山地上进行跑步锻炼，场地的高度和减速值分别由二维数组 $h$ 和 $o$ 记录。塔子哥初始速度为 $1$，当他从高度为 $h1$ 的位置移动到高度为 $h2$ 的相邻位置时，速度变化为 $h1 - h2 - o2$，其中 $o2$ 是目标位置的减速值。任务是计算塔子哥能够到达的速度仍为 $1$ 的位置数量。输入包含场地的大小、塔子哥的初始位置、高度值数组和减速值数组，输出为速度为 $1$ 的位置的个数。

思路

这是一道基于$BFS$的题目。主要考点为$BFS$。

这道题要我们找到所有速度为$1$的终点站的点的数量。那么我们需要知道所有终点站的速度，然后在这些速度中找到为$1$的点即可。

• 如何找到各个点的速度？
  • 假设我们目前处于点$u$，上下左右四个邻点记为$v$，那么假设我们知道点$u$的速度，$v$的速度就可以按照题目公式计算得到。因此，这里就需要用到$BFS$，对我们目前处于的点$u$进行$BFS$，得到周围所有点速度。然后我们计算得到速度后，对于速度为$1$的点进行记录即可。
• 如何记录速度为1的点？
  • 我们在$BFS$同时，一旦遇到点速度为$1$就需要判断该点对答案做不做贡献。一个点如果做贡献，那么说明在$BFS$过程中这个点第一次被判断为速度为$1$（即第二次和以后都不用记录贡献）。
• 如何处理$BFS$重复经过某点？
  • 和传统$BFS$不一样，传统$BFS$的处理是利用$map$存储$(x,y)$，只需要判断点$(x,y)$是否被经过（因为第一次到$(x,y)$和第二次到$(x,y)$并不影响$(x,y)$对于相邻点答案的影响），这道题假设我们判断又重复经过一个点$(x,y)$，但是具有不同的速度时，我们发现和传统$BFS$不一样，因为不同的速度会导致相邻点产生不一样的速度。因此这道题我们可以利用$map$存储$(x,y,v)$，$x,y$为对应的位置，$v$是对应的速度，只要位置与速度都一样时，那么对相邻点的影响一定是一样的。
• 如何判断点对于答案做不做贡献?
  • 我们利用上述的$map$存储对应的$(x,y,v)$，一旦重复经过$(x,y,z)$，我们就跳过，这样就保证每一个$(x,y,1)$都只会被记录一次即可。

代码

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tp = tuple<int, int, int>; // 用于表示位置和速度的三元组
const int dirs[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }; // 代表上下左右四个方向

int main() {
    int ans = 0; // 记录速度为1的点的数量
    char ch; 
    string s;
    
    // 读取场地大小 m 和 n
    cin >> s;
    int m = 0, n = 0;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            while (s[i] != ',') { // 读取 m
                m = m * 10 + s[i] - '0';
                ++i;
            }
            while (i < s.size() - 1) // 读取 n
                n = n * 10 + s[++i] - '0';
        }
    }
    
    // 读取塔子哥的初始位置
    int sx, sy;
    cin >> sx >> ch >> sy;
    
    // 初始化高度和减速值的二维数组
    vector<vector<pii>> grid(m, vector<pii>(n)); // 每个元素存储高度和减速值
    unordered_map<int, unordered_set<int>> mp; // 存储每个点的速度状态
    vector<int> ss(m * n); // 临时存储高度和减速值

    // 读取高度值
    int idx = 0;
    for (int i = 0; i < m * n; i++) {
        cin >> ss[i];
        if (i < m * n - 1)
            ch = getchar(); // 处理输入中的空格
    }
    
    // 将高度值存入grid
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j].first = ss[idx++];
        }
    }
    
    // 读取减速值
    for (int i = 0; i < m * n; i++) {
        cin >> ss[i];
        if (i < m * n - 1)
            ch = getchar(); // 处理输入中的空格
    }
    
    // 将减速值存入grid
    idx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j].second = ss[idx++];
        }
    }

    // BFS初始化
    queue<tp> q; // BFS队列
    q.push(tp{ sx, sy, 1 }); // 将初始点加入队列，速度为1
    mp[sx * n + sy].insert(1); // 记录初始点的速度

    // BFS过程
    while (!q.empty()) {
        tp cur = q.front(); // 获取当前点
        q.pop();
        
        for (int i = 0; i < 4; i++) { // 遍历四个方向
            int ni = get<0>(cur) + dirs[i][0]; // 新点的行坐标
            int nj = get<1>(cur) + dirs[i][1]; // 新点的列坐标
            
            // 检查新点是否越界
            if (ni >= m || ni < 0 || nj >= n || nj < 0)
                continue;
            
            int h1 = grid[get<0>(cur)][get<1>(cur)].first; // 当前点的高度
            int h2 = grid[ni][nj].first; // 新点的高度
            int o2 = grid[ni][nj].second; // 新点的减速值
            
            // 计算新点的速度
            int tmp = get<2>(cur) + (h1 - h2 - o2);
            
            // 若速度小于等于0或新点速度已记录，跳过
            if (tmp <= 0 || mp[ni * n + nj].count(tmp))
                continue;
                
            // 如果新点速度为1，答案加1
            if (tmp == 1)
                ++ans;
                
            // 记录新点的速度
            mp[ni * n + nj].insert(tmp);
            // 将新点加入队列
            q.push(tp{ ni, nj, tmp });
        }
    }
    
    // 输出结果
    std::cout << ans << endl;
    return 0;
}

python

from collections import defaultdict
import queue


def solv():
    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    q = queue.Queue()#开辟队列
    visited = defaultdict(int)#开辟字典
    q.put([start_x, start_y, 1])#队列put初始值
    visited[(start_x, start_y, 1)] = 1#字典记录

    cnt = 0
    while not q.empty():
        now = q.get()
        x, y, v = now[0], now[1], now[2]
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx > m - 1 or ny < 0 or ny > n - 1:
                continue#上述为队列经典操作
            nv = v + (mat_h[x][y] - mat_h[nx][ny] - mat_o[nx][ny])#计算速度
            if visited[(nx, ny, nv)] == 1 or nv < 1:#一旦发现(x,y,v)已经被记录或者v<=0时就跳过
                continue
            if nv == 1:#如果(x,y,1)第一次发生，答案就加1
                cnt += 1
            q.put([nx, ny, nv])#BFS经典操作
            visited[(nx, ny, nv)] = 1#更新map，存储每一个(x,y,v)
    print(cnt)


m, n = map(int, input().split(','))
start_x, start_y = map(int, input().split(','))
mat_h = [list(map(int, row.split(','))) for row in input().split(' ')]
mat_o = [list(map(int, row.split(','))) for row in input().split(' ')]
solv()
# by rivers (ps:有一定小修改)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
      
        String[] s = sc.nextLine().trim().split(",");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        s = sc.nextLine().trim().split(",");
        int sx = Integer.parseInt(s[0]), sy = Integer.parseInt(s[1]);
        int[][] h = new int[n][m], o = new int[n][m];
        s = sc.nextLine().trim().replace(" ", ",").split(",");
        for (int i = 0, idx = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                h[i][j] = Integer.parseInt(s[idx++]);
            }
        }
        s = sc.nextLine().trim().replace(" ", ",").split(",");
        for (int i = 0, idx = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                o[i][j] = Integer.parseInt(s[idx++]);
            }
        }//输入

        // 状态记录
        Map<Integer, Set<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map.put(i * m + j, new HashSet<>());//对于每一个点开辟一个set记录出现过的速度
            }
        }

        Queue<int[]> q = new LinkedList<>();//开辟队列
        map.get(sx * m + sy).add(1);
        q.offer(new int[]{sx, sy, 1});//初始点入队列
        int cnt = 0;
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int x = t[0], y = t[1], v = t[2];
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;//上面几句BFS经典操作
                int nv = v + h[x][y] - h[a][b] - o[a][b];//求得速度
                if (nv <= 0 || map.get(a * m + b).contains(nv)) continue;//一旦发现(x,y,v)已经被记录或者v<=0时就跳过
                
                if (nv == 1) cnt++;//如果(x,y,1)第一次发生，答案就加1
                map.get(a * m + b).add(nv);//更新map，存储每一个(x,y,v)
                q.offer(new int[]{a, b, nv});//BFS经典操作
            }
        }
        System.out.println(cnt);
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	s := scanner.Text()

	m, n := 0, 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] >= '0' && s[i] <= '9' {
			for s[i] != ',' {
				m = m*10 + int(s[i]-'0')
				i++
			}
			for i < len(s)-1 {
				n = n*10 + int(s[i+1]-'0')
				i++
			}
		}
	}

	scanner.Scan()
	s = scanner.Text()

	sx, _ := strconv.Atoi(strings.Split(s, ",")[0])
	sy, _ := strconv.Atoi(strings.Split(s, ",")[1])

	grid := make([][][2]int, m)//记录输入数组
	mp := make(map[int]map[int]bool)//开辟map

	
    scanner.Scan()
    s = scanner.Text()
    nums := strings.Fields(s)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            mp[i * n + j] = make(map[int]bool)
        }
    }
    for i := 0; i < m; i++ {
		grid[i] = make([][2]int, n)
        nums2 := strings.Split(nums[i], ",")
		for j := 0; j < n; j++ {
			grid[i][j][0], _ = strconv.Atoi(nums2[j])
		}
	}
    scanner.Scan()
    s = scanner.Text()
    nums3 := strings.Fields(s)
	for i := 0; i < m; i++ {
        nums4 := strings.Split(nums3[i], ",")
		for j := 0; j < n; j++ {
			grid[i][j][1], _ = strconv.Atoi(nums4[j])
		}
	}//输入
    

	q := make([][3]int, 0)
	q = append(q, [3]int{sx, sy, 1})//初始化队列
	mp[sx*n+sy][1] = true//初始化map
	ans := 0

	for len(q) > 0 {
		cur := q[0]
		q = q[1:]

		for i := 0; i < 4; i++ {
			ni := cur[0] + dirs[i][0]
			nj := cur[1] + dirs[i][1]

			if ni >= m || ni < 0 || nj >= n || nj < 0 {
				continue
			}//BFS基本操作

			h1 := grid[cur[0]][cur[1]][0]
			h2 := grid[ni][nj][0]
			o2 := grid[ni][nj][1]
			tmp := cur[2] + (h1 - h2 - o2)//得到速度

			if tmp <= 0 || mp[ni*n+nj][tmp] {//一旦发现(x,y,v)已经被记录或者v<=0时就跳过
				continue
			}

			if tmp == 1 {//如果(x,y,1)第一次发生，答案就加1
				ans++
			}

			mp[ni*n+nj][tmp] = true//更新map，存储每一个(x,y,v)
			q = append(q, [3]int{ni, nj, tmp})//BFS经典操作
		}
	}

	fmt.Println(ans)
}

Js

const readline = require('readline');

function main() {
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });

  let n, m;
  let sx, sy;
  let h, o;
  let map = new Map();

  rl.question('', (line) => {
    const s = line.trim().split(',');
    n = parseInt(s[0]);
    m = parseInt(s[1]);

    rl.question('', (line) => {
      const s = line.trim().split(',');
      sx = parseInt(s[0]);
      sy = parseInt(s[1]);

      h = new Array(n);
      o = new Array(n);

      rl.question('', (line) => {
        const s = line.trim().replace(/ /g, ',').split(',');
        let idx = 0;

        for (let i = 0; i < n; i++) {
          h[i] = new Array(m);
          for (let j = 0; j < m; j++) {
            h[i][j] = parseInt(s[idx++]);
          }
        }

        rl.question('', (line) => {
          const s = line.trim().replace(/ /g, ',').split(',');
          idx = 0;

          for (let i = 0; i < n; i++) {
            o[i] = new Array(m);
            for (let j = 0; j < m; j++) {
              o[i][j] = parseInt(s[idx++]);
            }
          }

          for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
              map.set(i * m + j, new Set());
            }
          }//输入开辟数组

          let q = [];//队列
          map.get(sx * m + sy).add(1);//map初始化
          q.push([sx, sy, 1]);//队列初始化
          let cnt = 0;
          let dx = [-1, 0, 1, 0];
          let dy = [0, 1, 0, -1];

          while (q.length > 0) {
            let t = q.shift();
            let x = t[0];
            let y = t[1];
            let v = t[2];

            for (let i = 0; i < 4; i++) {
              let a = x + dx[i];
              let b = y + dy[i];

              if (a < 0 || a >= n || b < 0 || b >= m) {
                continue;
              }//BFS基本操作

              let nv = v + h[x][y] - h[a][b] - o[a][b];//求得速度

              if (nv <= 0 || map.get(a * m + b).has(nv)) {
                continue;//一旦发现(x,y,v)已经被记录或者v<=0时就跳过
              }

              if (nv === 1) {
                cnt++;//如果(x,y,1)第一次发生，答案就加1
              }

              map.get(a * m + b).add(nv);//更新map，存储每一个(x,y,v)
              q.push([a, b, nv]);//BFS经典操作
            }
          }

          console.log(cnt);
          rl.close();
        });
      });
    });
  });
}

main();