内存限制: 65536KB
题目描述:
今天，我们要进入一个充满机器人的神奇科技世界。这是一张由小红科技总部最新研发的网络格地图。每个格子都绘制着标志——它们标示着机器人的行进方向；这些标志会让机器人进入它们指向的下一个相邻格子。
网格有 n 行 m 列的地图，左上角为 (1,1)，右下角为 (n,m)。每个格子有一个滑行带，前进方向为 L,R,U,D，分别表示左右上下四个方向。
- 如果滑出时刻，机器人位于 (i,j) 且滑行方向为 L，则第 t+1 时刻机器人位于 (i,j-1)。
- 如果滑出时刻，机器人位于 (i,j) 且滑行方向为 R，则第 t+1 时刻机器人位于 (i,j+1)。
- 如果滑出时刻，机器人位于 (i,j) 且滑行方向为 U，则第 t+1 时刻机器人位于 (i-1,j)。
- 如果滑出时刻，机器人位于 (i,j) 且滑行方向为 D，则第 t+1 时刻机器人位于 (i+1,j)。
已知滑行带不会让机器人滑出地图范围。地图最大行列不超过 (5 \times 10^5) 网格。地图上到达某个格子的机器人数量等于多少呢?
输入描述:
第一行两个整数 n m (1 <= n, m <= 3 * 10^5)，表示地图大小。
接下来 n 行，每行包含 m 个字符的字符串，表示每个格子滑行带的方向。
输出描述:
输出一行一个整数，表示第 10 时刻，地图上剩下机器人 A 的数量。
输入例子:
2 5
LRRLR
UULLR
输出例子:
6
#include <iostream>
#include <vector>using namespace std;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char dirs[4] = {'L', 'R', 'U', 'D'};int main() {int n, m;cin >> n >> m;vector<vector<char>> g(n, vector<char>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> g[i][j];}}vector<vector<long long>> cnt(n, vector<long long>(m, 1));for (long long t = 0; t < n + m; t++) {vector<vector<long long>> newCnt(n, vector<long long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (cnt[i][j] > 0) {char d = g[i][j];int idx = -1;for (int k = 0; k < 4; k++) {if (dirs[k] == d) {idx = k;break;}}int ni = i + dx[idx];int nj = j + dy[idx];if (ni >= 0 && ni < n && nj >= 0 && nj < m) {newCnt[ni][nj] += cnt[i][j];}}}}cnt = newCnt;}long long res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {res += cnt[i][j];}}cout << res << endl;return 0;
}