题解 - 迷宫

听风与你s6mi7 LV 6 @ 2025-3-26 17:05:46

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;
}

不拿国一不改名 LV 8 @ 2025-3-29 13:16:05

用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;
}

snowfish112 LV 8 @ 2025-3-25 22:49:08

#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;
}

qzhs LV 2 MOD @ 2025-3-10 22:09:33

解决思路

本题描述的是一个迷宫，由 $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()

ID

297

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

qzhs

4 条题解

解决思路

算法解释

迷宫

信息

工具

实用链接

QQ3号群

欢迎加入

QQ2号群

欢迎加入

QQ1号群

欢迎加入

在线询问

自动添加有问必答

4 条题解

解决思路

算法解释

迷宫

信息

工具

实用链接

QQ3号群

欢迎加入

QQ2号群

欢迎加入

QQ1号群

欢迎加入

在线询问

自动添加有问必答

微信登录

账号密码登录