解决思路

本题描述的是一个迷宫，由 $N$ 行 $M$ 列构成，每个格子可能为冰（.）或巨石（#）。迷宫外围全部为巨石，而起点固定为 $(2,2)$（保证为冰）。探险家可以沿着四个基本方向滑行：上、下、左、右，一旦选定方向，将一直滑行直到碰到巨石或遇到非冰格为止。题目要求计算探险家能够“触及或经过”的所有不同格子的总数。

解决该问题的关键在于考虑滑行过程中可能经过的所有格子，不仅是终点，还包括滑行路径上所有经过的冰面。为了避免重复计数，需要对每个格子是否访问过进行记录。另外，由于探险家每次滑行一旦确定方向就会一直前进，因此在搜索过程中不仅需要考虑当前位置，还需要记录其状态：是否处于“自由选择方向”（初始状态）还是处于“固定方向”滑行中。我们将固定方向的状态编号为 0 到 3，代表上、下、左、右，而状态 4 表示处于初始状态，可选择任意方向开始滑行。

数学上，我们可以设位置编号为 $p=x\cdot M+y$（其中 $x,y$ 为二维坐标），将状态编码为：

$$\text{state} = 5 \times (x \times M + y) + d,\quad d\in\{0,1,2,3,4\} $$

其中 $d=4$ 表示初始状态。利用广度优先搜索（BFS），从起点的状态（对应编号 $5 \times ((2-1)\times M+(2-1)) + 4$）开始，将可以滑行到的每个状态加入队列，并标记访问。遍历结束后，对每个格子，只需看其五个状态中是否至少有一个被访问，从而统计不同触及或经过的格子总数。

算法解释

本题的核心算法采用 BFS（宽度优先搜索）来遍历迷宫。由于探险家的滑行方式特殊，一旦选定方向就会持续前行直到遇到障碍，因此在 BFS 状态中需要记录“当前位置”和“当前滑行方向”。具体地，我们将状态编码为一个整数，形式为

$$\text{state} = 5 \times (x \times M + y) + d$$

其中 $d=4$ 代表初始状态，即探险家还未固定方向，可以从该状态选择任意四个方向开始滑行。若 $d\neq4$ 则说明探险家正沿着某一固定方向滑行。在初始状态下（$d=4$），我们尝试向四个方向滑行，若下一个格子为冰（.），则进入对应方向的状态；若已经在固定方向中，则继续沿同一方向滑行，直到碰到巨石（#）为止，一旦遇到障碍则返回到初始状态（即状态编号末尾设为4），重新可以选择其他方向。数学上，若当前位置为 $(x,y)$，沿方向 $d$ 滑行到 $(x+\Delta x, y+\Delta y)$，若该位置为冰，则状态变为

$$\text{new state} = 5 \times ((x+\Delta x) \times M + (y+\Delta y)) + d $$

若遇到障碍，则状态返回到初始状态：

$$\text{new state} = 5 \times (x \times M + y) + 4$$

整个搜索过程使用 BFS 保证每个状态只被访问一次，复杂度为 $O(NM)$。最终结果统计时，我们遍历所有格子，对于每个格子计算其五个状态是否至少有一个被访问，从而得出触及或经过该格子的判断。由于网格最大为 $200 \times 200$，总状态数不超过 $5 \times 200 \times 200=200000$，算法在数据范围内能够高效完成。

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (auto &nx : s) {
        cin >> nx;
    }

    vector<int> fl(5 * n * m, 0);
    queue<int> q;
    fl[5 * (m + 1) + 4] = 1;
    q.push(5 * (m + 1) + 4);

    while (!q.empty()) {
        int od = q.front();
        q.pop();
        int x = (od / 5) / m;
        int y = (od / 5) % m;
        int d = od % 5;

        if (d == 4) { // 初始探索
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nd = i;
                if (s[nx][ny] == '.') {
                    int nid = 5 * (nx * m + ny) + nd;
                    if (fl[nid] == 0) {
                        fl[nid] = 1;
                        q.push(nid);
                    }
                }
            }
        } else { // 持续沿当前方向移动
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (s[nx][ny] == '.') {
                int nid = 5 * (nx * m + ny) + d;
                if (fl[nid] == 0) {
                    fl[nid] = 1;
                    q.push(nid);
                }
            } else { // 碰到障碍物
                int nid = 5 * (x * m + y) + 4;
                if (fl[nid] == 0) {
                    fl[nid] = 1;
                    q.push(nid);
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n * m; i++) {
        res += max({fl[5 * i], fl[5 * i + 1], fl[5 * i + 2], fl[5 * i + 3], fl[5 * i + 4]});
    }

    cout << res << "\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine();
        }
        
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        int size = 5 * n * m;
        int[] fl = new int[size];
        // 起点 (2,2) 对应索引 (1,1)；编码为 5*((1)*m + 1) + 4 = 5*(m+1)+4
        int start = 5 * (m + 1) + 4;
        fl[start] = 1;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        
        while (!q.isEmpty()) {
            int od = q.poll();
            int pos = od / 5;
            int d = od % 5;
            int x = pos / m;
            int y = pos % m;
            if (d == 4) { // 初始探索状态
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    int nd = i;
                    if (s[nx].charAt(ny) == '.') {
                        int nid = 5 * (nx * m + ny) + nd;
                        if (fl[nid] == 0) {
                            fl[nid] = 1;
                            q.add(nid);
                        }
                    }
                }
            } else { // 固定方向滑行状态
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (s[nx].charAt(ny) == '.') {
                    int nid = 5 * (nx * m + ny) + d;
                    if (fl[nid] == 0) {
                        fl[nid] = 1;
                        q.add(nid);
                    }
                } else { // 遇到障碍物，返回初始状态
                    int nid = 5 * (x * m + y) + 4;
                    if (fl[nid] == 0) {
                        fl[nid] = 1;
                        q.add(nid);
                    }
                }
            }
        }
        
        int res = 0;
        for (int i = 0; i < n * m; i++) {
            int maxv = Math.max(Math.max(fl[5 * i], fl[5 * i + 1]), Math.max(fl[5 * i + 2], Math.max(fl[5 * i + 3], fl[5 * i + 4])));
            res += (maxv > 0 ? 1 : 0);
        }
        
        out.println(res);
        out.flush();
    }
}

import sys
from collections import deque

def main():
    data = sys.stdin.read().splitlines()
    n, m = map(int, data[0].split())
    s = data[1:1+n]
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    size = 5 * n * m
    fl = [0] * size
    # 起点 (2,2) 对应于下标 (1,1) ，编码为 5*((1)*m + 1)+4 = 5*(m+1)+4
    start = 5 * (m + 1) + 4
    fl[start] = 1
    q = deque([start])
    
    while q:
        od = q.popleft()
        pos = od // 5
        d = od % 5
        x = pos // m
        y = pos % m
        if d == 4:  # 初始状态
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                nd = i
                if s[nx][ny] == '.':
                    nid = 5 * (nx * m + ny) + nd
                    if fl[nid] == 0:
                        fl[nid] = 1
                        q.append(nid)
        else:  # 固定方向滑行
            nx = x + dx[d]
            ny = y + dy[d]
            if s[nx][ny] == '.':
                nid = 5 * (nx * m + ny) + d
                if fl[nid] == 0:
                    fl[nid] = 1
                    q.append(nid)
            else:  # 碰到障碍，回到初始状态
                nid = 5 * (x * m + y) + 4
                if fl[nid] == 0:
                    fl[nid] = 1
                    q.append(nid)
    
    res = 0
    for i in range(n * m):
        if max(fl[5*i], fl[5*i+1], fl[5*i+2], fl[5*i+3], fl[5*i+4]) > 0:
            res += 1
    sys.stdout.write(str(res))

if __name__ == "__main__":
    main()