题目分析

给定一个$n \times m$的网格，其中每个位置可能是可通行的空方格（0）或是地雷方格（1）。我们需要找到有多少个地雷方格能够消灭影子怪兽。我们从网格的中点出发，怪兽从网格中点的右下方出发。每次你移动一步，怪兽会做相反的动作，目标是通过踩到地雷方格来消灭怪兽。与此同时，你必须保证自己的移动不进入地雷方格。

思路

1. 模拟移动过程

我们可以通过模拟网格中的移动过程来解这个问题。关键的思想是你和怪兽总是做相反的移动，因此你可以通过遍历你的每一次可能的合法移动来判断怪兽是否会被消灭。

• 你从初始位置$(\frac{n}{2}, \frac{m}{2})$出发，怪兽从$(\frac{n}{2}+1, \frac{m}{2}+1)$出发。
• 每次你移动时，怪兽也会做相反的动作。
• 如果在某个点，你的移动和怪兽的反向移动将怪兽推入一个地雷方格，并且你不走进地雷方格，就可以消灭怪兽。

2. 使用广度优先搜索（BFS）

可以通过广度优先搜索（BFS）来遍历所有可能的状态。在每一步，记录你和怪兽的当前位置，并计算你能否通过移动到某个格子来触发怪兽进入地雷方格。BFS的好处是它能够层层推进，确保能够找到所有可能的消灭怪兽的路径。

• 我们维护一个队列，队列中的元素是当前你和怪兽的位置。
• 使用一个vis数组记录哪些位置已经被访问过，以避免重复计算。
• 对于每一步，我们尝试四个方向的移动，如果移动不出界且不会踩到地雷，就将新的状态加入队列。

3. 终止条件

当你访问到一个合法的地雷方格时，怪兽就会被消灭。

4. 时间复杂度

• 网格的最大大小为$10^6$，因此我们需要高效的算法来处理。BFS的时间复杂度为$O(n \times m)$，在最坏情况下需要遍历所有的网格位置。由于我们在队列中维护了每一个状态，因此时间复杂度是可接受的。

代码实现

Python代码

from collections import deque

# 输入
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

# 初始化BFS
q = deque([(n//2-1, m//2-1, n//2, m//2)])  # (玩家位置, 怪兽位置)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
vis = [[False] * m for _ in range(n)]
ans = 0

# BFS遍历
while q:
    x1, y1, x2, y2 = q.popleft()
    
    # 如果当前位置已经被访问过，跳过
    if vis[x1][y1]:
        continue
    
    # 标记玩家当前位置为访问过
    vis[x1][y1] = True
    
    # 如果怪兽当前在地雷方格，则可以消灭怪兽
    if grid[x2][y2] == 1:
        ans += 1
        continue
    
    # 尝试四个方向的移动
    for i in range(4):
        nx1, ny1 = x1 + dx[i], y1 + dy[i]  # 玩家新的位置
        nx2, ny2 = x2 - dx[i], y2 - dy[i]  # 怪兽新的位置
        
        # 如果新的位置出界或玩家走到地雷方格，跳过
        if not (0 <= nx1 < n and 0 <= ny1 < m) or not (0 <= nx2 < n and 0 <= ny2 < m) or grid[nx1][ny1] == 1:
            continue
        
        # 添加新的状态到队列
        q.append((nx1, ny1, nx2, ny2))

# 输出结果
print(ans)

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        // 初始化BFS
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{n / 2 - 1, m / 2 - 1, n / 2, m / 2});  // (玩家位置, 怪兽位置)
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        boolean[][] vis = new boolean[n][m];
        int ans = 0;
        
        // BFS遍历
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int x1 = pos[0], y1 = pos[1], x2 = pos[2], y2 = pos[3];
            
            // 如果当前位置已经被访问过，跳过
            if (vis[x1][y1]) {
                continue;
            }
            
            // 标记玩家当前位置为访问过
            vis[x1][y1] = true;
            
            // 如果怪兽当前在地雷方格，则可以消灭怪兽
            if (grid[x2][y2] == 1) {
                ans++;
                continue;
            }
            
            // 尝试四个方向的移动
            for (int i = 0; i < 4; i++) {
                int nx1 = x1 + dx[i], ny1 = y1 + dy[i];  // 玩家新的位置
                int nx2 = x2 - dx[i], ny2 = y2 - dy[i];  // 怪兽新的位置
                
                // 如果新的位置出界或玩家走到地雷方格，跳过
                if (nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m || nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m || grid[nx1][ny1] == 1) {
                    continue;
                }
                
                // 添加新的状态到队列
                q.offer(new int[]{nx1, ny1, nx2, ny2});
            }
        }
        
        // 输出结果
        System.out.println(ans);
    }
}

C++代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 初始化BFS
    queue<vector<int>> q;
    q.push({n / 2 - 1, m / 2 - 1, n / 2, m / 2});  // (玩家位置, 怪兽位置)
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    int ans = 0;

    // BFS遍历
    while (!q.empty()) {
        auto pos = q.front();
        q.pop();
        int x1 = pos[0], y1 = pos[1], x2 = pos[2], y2 = pos[3];

        // 如果当前位置已经被访问过，跳过
        if (vis[x1][y1]) {
            continue;
        }

        // 标记玩家当前位置为访问过
        vis[x1][y1] = true;

        // 如果怪兽当前在地雷方格，则可以消灭怪兽
        if (grid[x2][y2] == 1) {
            ans++;
            continue;
        }

        // 尝试四个方向的移动
        for (int i = 0; i < 4; i++) {
            int nx1 = x1 + dx[i], ny1 = y1 + dy[i];  // 玩家新的位置
            int nx2 = x2 - dx[i], ny2 = y2 - dy[i];  // 怪兽新的位置

            // 如果新的位置出界或玩家走到地雷方格，跳过
            if (nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m || nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m || grid[nx1][ny1] == 1) {
                continue;
            }

            // 添加新的状态到队列
            q.push({nx1, ny1, nx2, ny2});
        }
    }

    // 输出结果
    cout << ans << endl;

    return 0;
}

题目内容

给定一个$n$行$m$ 列的网格，且保证$n,m$都为偶数。我们用$(i,j)$表示第$i$行第$j$列的单元格。

每个单元格要么是可通行的空方格$0$，要么是不可通行的地雷方格$1$。

网格的四周都是墙，你可以在空方格上上下左右移动:

• 从$(x,y)$向上移动到$(x- 1,y)$;

• 向下移动到$(x+1,y)$;

• 向左移动到$(x,y-1)$;

• 向右移动到$(x,y+1)$。

你初始位于$(\frac{n}{2},\frac{m}{2})$，影子怪兽初始位于$(\frac{n}{2}+1,\frac{m}{2}+1)$

每当你移动一次，怪兽就朝相反方向移动一次，直到怪兽被消灭。

由于它始终和你做相反移动，无法被你直接追上。

不过，网格中有地雷方格可以消灭它。

请计算有多少不同的地雷方格可以消灭影子怪兽。你需要保证自己始终不会踏入地雷方格。

输入描述

第一行输入两个整数$n,m(4 ≤n×m≤10^6)$,表示网格大小。题目保证$n,m$都为偶数。

接下来$n$行，每行输入$m$个整数$a_{i,j}∈${$0,1$}，表示网格:

• $0$表示空方格;

• $1$表示地雷方格。

同时保证你和影子怪兽的初始位置所在单元格均为$0$

输出描述

输出一个整数，表示可以用来消灭影子怪兽的地雷方格总数。

样例1

输入

4 2
1 0
0 0 
1 0
1 1

输出

1

说明

• 你可以向右移动一格此时怪兽向左移动一格到达地雷被消灭，而你无法向上移动因为你上方是一个地雷方格。

样例2

输入

2 2
0 0 
0 0

输出

0

说明

• 此时网格中无地雷方格。
• 无法消灭怪兽,答案为$0$。