[CSP-J 2024] 地图探险 游记

Ren_Hx · 2024-10-26 23:01:11 · 生活·游记

考场思路

考场上第一眼看上去像是洪水填充，写完后测第五个样例才发现 n\le10^3,m\le10^3 ,要用模拟大法，不然爆栈空间。

考场分析

• 输入的处理

  输入的是字符串，不好操作，我们可以它们转换成数字存入二维数组里：

  vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
  //用循环输入一个地图
  for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if (ch == '.') a[i][j] = -1;//这是空地 
            else a[i][j] = 1;//这是障碍 
      }
  }

• 地图初始化

  先定义一个标记数组和两个方向数组，再记录下机器人的初始位置：

  set<pair<int, int>> s; // 用于记录经过的位置
  // 方向数组，0=东，1=南，2=西，3=北
  int dx[] = {0, 1, 0, -1};
  int dy[] = {1, 0, -1, 0};
  // 记录初始位置
  s.insert({x, y});

• 地图的处理

  用一个循环 k 次的 for ，里面先计算下一步的位置，然后检查下一步是否合法，合法就移到下一步，否则就向右转。

  for (int i = 0; i < k; i++) {
     int nx = x + dx[d]; // 计算下一步的位置
     int ny = y + dy[d];
     // 检查下一步的位置是否合法
     if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == -1) {
     // 如果合法，移动到下一步
     x = nx;
     y = ny;
     s.insert({x, y}); // 记录经过的位置
     } else {
     // 如果不合法，向右转
     d = (d + 1) % 4;
     }
  }

  考场代码

  
  #include <bits/stdc++.h>
  using namespace std;
  int main() {
  int T;
  cin >> T;
  while (T--) {
  int n, m, k, x, y, d;
  cin >> n >> m >> k >> x >> y >> d;
  vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
  set<pair<int, int>> s;
  for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
  char ch;
  cin >> ch;
  if (ch == '.') a[i][j] = -1;
  else a[i][j] = 1;
  }
  }
  int dx[] = {0, 1, 0, -1};
  int dy[] = {1, 0, -1, 0};
  s.insert({x, y});
  for (int step = 0; step < k; step++) {
  int nx = x + dx[d];
  int ny = y + dy[d];
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == -1) {
  x = nx;
  y = ny;
  s.insert({x, y});
  } else {
  d = (d + 1) % 4;
  }
  }
  cout << s.size() << endl;
  }
  return 0;
  }