dfs解法：（相对于正常的vis访问数组，本题的vis要多一个维度，因为某一点点的访问情况跟方向有关，所以要加上4个方向） ``` #include <iostream> using namespace std; const int N = 201; int m,n; char mp[N][N]; bool vis[N][N][4]; int dir[4][2] = {-1,0,1,0,0,1,0,-1}; void dfs(int x,int y,int d) { int nx = x + dir[d][0]; int ny = y + dir[d][1]; if(mp[nx][ny] == '.' && !vis[nx][ny][d]) { vis[nx][ny][d] = true; dfs(nx,ny,d); } if(mp[nx][ny] == '#') { for(int i = 0;i<4;i++) { nx = x + dir[i][0]; ny = y + dir[i][1]; if(mp[nx][ny] == '.' && !vis[nx][ny][i]) { vis[nx][ny][i] = true; dfs(nx,ny,i); } } } } int main() { cin>>n>>m; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) cin>>mp[i][j]; } if(mp[2][1] == '.') { vis[1][1][1] = true; dfs(1,1,1); } if(mp[1][2] == '.') { vis[1][1][2] = true; dfs(1,1,2); } int ans = 1; for(int i = 1;i<n-1;i++) { for(int j = 1;j<m-1;j++) { for(int k = 0;k<4;k++) { if(i == 1 && j == 1) continue; if(mp[i][j] == '.' && vis[i][j][k]) { ans++; break; } } } } cout<<ans; return 0; } ```

解决思路 本题描述的是一个迷宫，由 $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$，算法在数据范围内能够高效完成。 ```cpp #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; } ``` ```java 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(); } } ``` ```python 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() ```

用bfs模拟，本题是朝一个方向一直走，所以需要维护一个路径，还需要维护一个停止的点，因为只需要将到停止的点加入到队列中 ``` #include<cstdio> #include<iostream> #include<vector> #include<map> #include<cstring> #include<array> #include<queue> #include<algorithm> #include<set> #include<cmath> using namespace std; using i64=long long; //using i128=__int128; const i64 INF=1e18; const int mod=998244353; //const int N=1e9+7; void solve(){ int n,m; cin>>n>>m; vector<vector<char> >g(n+1,vector<char>(m+1)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; } } vector<vector<int> >vis(n+1,vector<int>(m+1)),stop(n+1,vector<int>(m+1)); queue<pair<int,int> >q; int ans=0; q.push({2,2}); vis[2][2]=1; stop[2][2]=1;//记录停止点，将停止点加入到数组中 int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; ans++; while(!q.empty()){ auto [x,y]=q.front(); q.pop(); for(int i=0;i<4;i++){ //由于是要往一个方向移动，所以需要用一个临时变量 int nx=x,ny=y; vector<pair<int,int> >path; path.push_back({nx,ny}); while(1){ //一直往一个方向移动，直到撞到石头 int _nx=dx[i]+nx,_ny=dy[i]+ny; if(_nx<1||_nx>n||_ny<1||_ny>m||g[_nx][_ny]=='#')break; //记录路径 path.push_back({_nx,_ny}); //更新nx，ny nx=_nx,ny=_ny; } for(auto [_x,_y]:path){ if(!vis[_x][_y]){ vis[_x][_y]=1; ans++; } } //将终点入队 if(!stop[nx][ny]){ stop[nx][ny]=1; q.push({nx,ny}); } } } cout<<ans<<'\n'; } int main(){ int _=1; //cin>>_; while(_--)solve(); return 0; } ```

``` #include<bits/stdc++.h> using namespace std; int n,m; const int N=300; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; queue<vector<int>> q; int main() { cin>>n>>m; vector<vector<vector<int>>> f(n,vector<vector<int>>(m,vector<int>(5,0))); //存储x,y,当前状态,状态为4时选择0-3四个方向 vector<vector<char>> s(n,vector<char>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>s[i][j]; f[1][1][4]=1;//下标从0开始 q.push({1,1,4}); while(q.size()) { vector<int> cur=q.front(); q.pop(); int x=cur[0]; int y=cur[1]; int d=cur[2]; if(d==4)//选方向 { for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; int nd=i; if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]=='.') { if(f[nx][ny][nd]==0) { f[nx][ny][nd]=1; q.push({nx,ny,nd}); } } } } else//固定路线一直走 { int nx=x+dx[d]; int ny=y+dy[d]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]=='.') { if(f[nx][ny][d]==0) { f[nx][ny][d]=1; q.push({nx,ny,d}); } } else//到边界 { if(f[x][y][4]==0) { f[x][y][4]=1; q.push({x,y,4}); } } } } int ans=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { for(int d=0;d<5;d++) { if(f[i][j][d]==1) { ans++; break;//防重复，当前坐标下有一个方向标记即可 } } } } cout<<ans; return 0; } ```