学习 › JavaScript
算法 · 26
模拟与暴力枚举
照着题目的故事一步一步做，把候选一个不漏地都试一遍。
算法的第一步是不耍小聪明。
下面例子里的机器人在一条有 1 到 n 号格子的走廊上，按 L（左）、R（右）的命令每次走一格，被墙挡住就留在原地。
程序输出命令结束时机器人正好停在 goal 号格子的所有出发格，最后输出它们的个数。
n, goal = map(int, input().split())moves = input().strip()count = 0for start in range(1, n + 1): # 모두 해 보기: 출발 칸 후보 n개 pos = start # 후보마다 처음부터 다시 for m in moves: # 그대로 따라 하기: 명령 하나에 한 걸음 if m == "L" and pos > 1: pos -= 1 elif m == "R" and pos < n: pos += 1 if pos == goal: print(start) count += 1print(count)const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves = lines[1].trim();let count = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves: string = lines[1].trim();let count: number = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos: number = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), goal = sc.nextInt(); String moves = sc.next(); int count = 0; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves.toCharArray()) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { System.out.println(start); count++; } } System.out.println(count); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' '); int n = int.Parse(first[0]), goal = int.Parse(first[1]); string moves = Console.ReadLine().Trim(); int count = 0; for (int start = 1; start <= n; start++) // 모두 해 보기: 출발 칸 후보 n개 { int pos = start; // 후보마다 처음부터 다시 foreach (char m in moves) // 그대로 따라 하기: 명령 하나에 한 걸음 { if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { Console.WriteLine(start); count++; } } Console.WriteLine(count); }}#include <iostream>#include <string> int main() { int n, goal, count = 0; std::string moves; std::cin >> n >> goal >> moves; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { std::cout << start << '\n'; count++; } } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, goal, count = 0; char moves[1001]; scanf("%d %d %1000s", &n, &goal, moves); for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (int i = 0; moves[i] != '\0'; i++) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (moves[i] == 'L' && pos > 1) pos--; else if (moves[i] == 'R' && pos < n) pos++; } if (pos == goal) { printf("%d\n", start); count++; } } printf("%d\n", count); return 0;}first = 控制台.读数字();n = first[0];goal = first[1];moves = 控制台.读行().去空白();count = 0;循环 (start = 1; start <= n; start++){ pos = start; // 후보마다 처음부터 다시 遍历 (m 在 moves) { 如果 (m == "L" && pos > 1) { pos -= 1; } 否则 如果 (m == "R" && pos < n) { pos += 1; } } 如果 (pos == goal) { 控制台.输出(start); count += 1; }}控制台.输出(count);6 3 LLLRR
1 2 3 4 4
要点
- 模拟就是把题目的故事按原来的顺序写成代码。
把当前状态放在变量里（这里是机器人的位置pos），每一步按规则修改它。
因为有墙，“右的次数 − 左的次数”这样的式子得不到答案，老老实实走一遍最可靠。 - 暴力枚举（穷举）是把可能成为答案的候选一个不漏地试一遍，只留下符合条件的。
这里的候选是出发格 1 到 n。
没有漏掉的候选，就不会漏掉答案。 - 每个候选都要把状态恢复到开头。
这就是例子里pos = start写在外层循环里面的原因。 - 动手之前先数一数要走多少步：候选数 × 每个候选要走的步数。
这个例子是 n × 命令数。
从 n 个里选两个有 n × (n − 1) ÷ 2 对（n 为 200 时是 19,900 对），选或不选决定 n 次有 2ⁿ 种（n 为 20 时约 100 万），排成一排的顺序有 n!
种（n 为 10 时约 360 万）。 - 这里的一步指把一条命令执行一次（内层循环转一圈）。
用这个例子在我们的评测机上实测：1 千万步（1 万个格子 × 1 千条命令）八种语言都在 1 秒内跑完。
1 亿步（1 万个格子 × 1 万条命令）时，C、C++、Java、C# 在 1 秒内跑完，JavaScript、TypeScript 约 1 秒，但 Python 超过了 4 秒的时间限制。
Craykon 跑完了 4 千万步，到 5 千万步时提示“耗时太长”而停止。 - 步数宽裕时，暴力枚举就够了。
步数太多时才去找更快的方法，那时慢的解法还可以用来在小输入上核对快解法的答案。
各语言的写法
| Python | 在 for start in range(1, n + 1): 里用 pos = start 恢复，命令用 for m in moves: 逐个字符读。选两个用 itertools.combinations(nums, 2)，所有顺序用 itertools.permutations(nums) |
|---|---|
| JavaScript | 在 for (let start = 1; start <= n; start++) 里写 let pos = start;，命令用 for (const m of moves)。选两个时内层循环从 let j = i + 1 开始 |
| TypeScript | 和 JavaScript 一样 |
| Java | 把 int pos = start; 放在外层循环里，命令用 for (char m : moves.toCharArray())。字符用单引号比较（ m == 'L'） |
| C# | 把 int pos = start; 放在外层循环里，命令用 foreach (char m in moves)。字符写作 'L' |
| C++ | 命令用 for (char m : moves)，字符写作 'L'。要枚举所有顺序，先把 vector 排好序，再反复调用 std::next_permutation(v.begin(), v.end()) 直到它返回假 |
| C | 命令用 for (int i = 0; moves[i] != '\0'; i++) — 按下标循环到字符串结束标记 '\0'。字符写作 'L' |
| Craykon | 在 循环 (start = 1; start <= n; start++) 里写 pos = start;，命令用 遍历 (m 在 moves)。一次运行能走的步数有上限，超过就提示“耗时太长(无限循环?)”并停止 |
常见错误
没有为每个候选恢复状态
let sum = 0;
for (let x = 10; x <= 12; x++) {
for (const d of String(x)) sum += Number(d);
console.log(x, sum);
}→ 10 1、11 3、12 6 — 各位数字之和应该是 1、2、3，但上一个候选的和还留着，越加越多
把 let sum = 0; 移到外层循环里面，让每个候选都从 0 开始。
选两个时把同一对数了两次
int nums[] = {1, 2, 3, 4}, count = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (nums[i] + nums[j] == 4) count++;
printf("%d\n", count);→ 3 — 和为 4 的只有 (1, 3) 这一对，却把反过来的 (3, 1) 和自己配自己的 (2, 2) 也数进去了
内层循环从 j = i + 1 开始。
每一对只看一次，也不会自己配自己，结果是 1。
一边改格子一边读邻居
cells = list("O..")
for i in range(3):
left = i > 0 and cells[i - 1] == "O"
right = i < 2 and cells[i + 1] == "O"
cells[i] = "O" if cells[i] == "." and left != right else "."
print("".join(cells))→ ... — 答案是 .O.。规则是“亮的格子熄灭，灭的格子在恰好有一个亮着的邻居时点亮”（left != right 表示“恰好一个”），而且所有格子要同时变化。可是 0 号格子先被熄灭了，等 1 号格子去看邻居时，它已经是灭的
把下一个状态写到新列表里，写完再整体换上。
先建 after = []，用 after.append(...) 收集，循环结束后 cells = after。
这样结果是 .O.。
各语言的差异
养成先按题目给的输入规模数步数的习惯。
步数宽裕时，最简单的解法就是最好的解法。
模拟的答案不对时，拿一个小输入用手一步一步走，和变量的值对照。
先看墙这样的边界处有没有差一格。
养成先按题目给的输入规模数步数的习惯。
步数宽裕时，最简单的解法就是最好的解法。
模拟的答案不对时，拿一个小输入用手一步一步走，和变量的值对照。
先看墙这样的边界处有没有差一格。