笔试时间：2024年09月08日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：机器人

小红书的冒险家们！今天，我们要进入一个充满挑战的高科技迷言。这是一张由小红书科技部最新研发的网格地图，每个格子都营着秘密一它们内置了自动滑行带！这些滑行带会让所有进入它们的机器人自动翻一个特定方向滑行。网格地图每个格子都藏着秘密一它们内置了自动滑行带！这些滑行带会让所有进入它们的机器人自动朝一个特定方向滑行。具体来说，一张n*m的网格地图，左上角为(1,1)，右下角为(n,m),每个格子有一个滑行带，前进方向为L,R,U,D,分别表示左右上下四个方向前进。

• 如果第t时刻，机器人位于(i,j),(i,j)滑行带前进方向为L,则第t+1时刻机器人位于(i,j-1),
• 如果第t时刻，机器人位于(i,j),(i,j)滑行带前进方向为R,则第t+1时刻机器人位于(i,j+1)
• 如果第t时刻，机器人位于(i,j),(i,j)小滑行带前进方向为U,则第t+1时刻机器人位于(i-1,j)
• 如果第t时刻，机器人位于(i,j),(i,j)小滑行带前进方向为D,则第t+1时刻机器人位于(i+1,j)。

机器人走出地图后就会毁坏，一个格子可以容纳多个机器人。第0时刻，每个位置都有一个机器人，问：第10^8时刻，地图上还剩下多少个机器人？

输入描述

第一行两个整数nm(1≤nm≤510^3)，表示地图大小。

接下来n行，每行一个包含m个字符的字符串，表示每个格子滑行带的方向。

输出描述

输出一行一个整数，表示第10^8时刻，地图上剩下机器人的数量。

样例输入

2 5

LRRLR 

UULLR 

样例输出

6

参考题解

dfs。读取网格地图中每个格子的滑行带方向 (L, R, U, D)，然后使用深度优先搜索 (DFS) 追踪每个格子的运动轨迹，记录它是否会滑出地图边界或进入一个循环。具体来说，对每个格子，DFS 会判断机器人是否会进入循环状态或者滑出边界，通过一个二维数组 vis标记每个格子的状态：0表示未访问，1表示已访问且在地图内，-1表示滑出了地图边界。最后，统计所有标记为 1的格子数，这些格子的机器人在第10^8时刻仍然在地图上。这样，我们能够有效地计算出剩余的机器人数量。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> mp;
vector<vector<int>> vis;
int n, m;
pair<int, int> move(int x, int y) {
 if (mp[x][y] == 'U') {
  return { x - 1,y };
 }
 if (mp[x][y] == 'D') {
  return { x + 1,y };
 }
 if (mp[x][y] == 'L') {
  return { x,y - 1 };
 }
 if (mp[x][y] == 'R') {
  return { x,y + 1 };
 }
 return { x,y };
}
int dfs(int x, int y) {
 if (vis[x][y]) {
  return vis[x][y];
 }
 vis[x][y] = 1;
 pair<int, int> next = move(x, y);
 if (next.first < 0 || next.first >= n || next.second < 0 || next.second >= m) {
  return vis[x][y] = -1;
 }
 return vis[x][y] = dfs(next.first, next.second);
}

int main() {
 cin >> n >> m;
 mp.resize(n, vector<char>(m));
 vis.resize(n, vector<int>(m));
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   cin >> mp[i][j];
  }
 }
 int ans = 0;
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   if (dfs(i, j) == 1) {
    ans++;
   }
  }
 }
 cout << ans << endl;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    static char[][] mp;
    static int[][] vis;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        mp = new char[n][m];
        vis = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < m; j++) {
                mp[i][j] = line.charAt(j);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(i, j) == 1) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
        sc.close();
    }

    public static int dfs(int x, int y) {
        if (vis[x][y] != 0) {
            return vis[x][y];
        }
        vis[x][y] = 1;
        int[] next = move(x, y);

        if (next[0] < 0 || next[0] >= n || next[1] < 0 || next[1] >= m) {
            return vis[x][y] = -1;
        }

        return vis[x][y] = dfs(next[0], next[1]);
    }

    public static int[] move(int x, int y) {
        if (mp[x][y] == 'U') {
            return new int[]{x - 1, y};
        }
        if (mp[x][y] == 'D') {
            return new int[]{x + 1, y};
        }
        if (mp[x][y] == 'L') {
            return new int[]{x, y - 1};
        }
        if (mp[x][y] == 'R') {
            return new int[]{x, y + 1};
        }
        return new int[]{x, y};
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def move(x, y):
    if mp[x][y] == 'U':
        return x - 1, y
    if mp[x][y] == 'D':