Chapter3——基础算法——模拟

1. 题目列表

• POJ1068（简单模拟）
• POJ2632（二维网格中的模拟，包括转向、行走等）
• POJ1573
• POJ2993(待完成)
• POJ2996(待完成)

2. POJ1068——Parencodings

2.1 题目描述

Description

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:

S       (((()()())))

P-sequence      4 5 6666

W-sequence      1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input

2
6
4 5 6 6 6 6
9 
4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

2.2 解决思路

该题给除了括号字符串S的P序列表达式，求该括号的W序列表达式，基本思路是根据P序列构造出原S串，根据规则求出W串。（简单模拟）

2.3 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 30;
char s[maxn];
int p[maxn];
vector<int> w;
bool visited[maxn];

int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int n;
        scanf("%d",&n);
        int k = 0;
        fill(visited, visited + maxn, false);
        w.clear();
        for (int i = 0; i < n; i++){
            scanf("%d",&p[i]);
            if (i > 0){
                for (int j = 0; j < p[i] - p[i - 1]; j++)
                    s[k++] = '(';
            }else{
                for (int j = 0; j < p[i]; j++)
                    s[k++] = '(';
            }
            s[k++] = ')';
        }
        for (int i = 0; i < k; i++){
            if (s[i] == ')'){
                int cnt = 1;
                // 向左循环找到第一个未访问过的左括号
                for (int j = i - 1; j >= 0; j--){
                    if (s[j] == '('){ // 碰到左括号 
                        if (!visited[j]){
                            visited[j] = true;
                            break;
                        }
                    }else{
                        cnt ++;
                    }
                } 
                w.push_back(cnt);
            }
        }
        for(int i = 0; i < w.size(); i++){
            printf("%d", w[i]);
            if (i != w.size() -1)
                printf(" ");
            else{
                printf("\n");
            }
        }
    }   
}

3. POJ2632——Crashing

3.1 题目描述

Description

In a modernized warehouse, robots are used to fetch the goods. Careful planning is needed to ensure that the robots reach their destinations without crashing into each other. Of course, all warehouses are rectangular, and all robots occupy a circular floor space with a diameter of 1 meter. Assume there are N robots, numbered from 1 through N. You will get to know the position and orientation of each robot, and all the instructions, which are carefully (and mindlessly) followed by the robots. Instructions are processed in the order they come. No two robots move simultaneously; a robot always completes its move before the next one starts moving.
A robot crashes with a wall if it attempts to move outside the area of the warehouse, and two robots crash with each other if they ever try to occupy the same spot.

Input

The first line of input is K, the number of test cases. Each test case starts with one line consisting of two integers, 1 <= A, B <= 100, giving the size of the warehouse in meters. A is the length in the EW-direction, and B in the NS-direction.
The second line contains two integers, 1 <= N, M <= 100, denoting the numbers of robots and instructions respectively.
Then follow N lines with two integers, 1 <= Xi <= A, 1 <= Yi <= B and one letter (N, S, E or W), giving the starting position and direction of each robot, in order from 1 through N. No two robots start at the same position.

image

Figure 1: The starting positions of the robots in the sample warehouse

Finally there are M lines, giving the instructions in sequential order.
An instruction has the following format:
< robot #> < action> < repeat>
Where <action>is one of

• L: turn left 90 degrees,

• R: turn right 90 degrees, or

• F: move forward one meter,

and 1 <= < repeat> <= 100 is the number of times the robot should perform this single move.</action>

Output

Output one line for each test case:

• Robot i crashes into the wall, if robot i crashes into a wall. (A robot crashes into a wall if Xi = 0, Xi = A + 1, Yi = 0 or Yi = B + 1.)

• Robot i crashes into robot j, if robots i and j crash, and i is the moving robot.

• OK, if no crashing occurs.

Only the first crash is to be reported.

Sample Input
4
5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7
5 4
2 4
1 1 E
5 4 W
1 F 3
2 F 1
1 L 1
1 F 3
5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2
5 4
2 3
1 1 E
5 4 W
1 F 4
1 L 1
1 F 20

Sample Output

Robot 1 crashes into the wall
Robot 1 crashes into robot 2
OK
Robot 1 crashes into robot 2

3.2 解决思路

该问题模拟在二维网格中的机器人的行走和转向问题。有以下的关键点需要解决：

• 机器人的转向操作。定义机器人的四个方向为0，1，2，3对应NESW
  左转操作为：direct = (direct + 3) % 4
  右转操作为：direct = (direct + 1) % 4
• 机器人的前进操作 。

3.3 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
/*
    坐标移动操作，转向操作，明天继续 
    定义机器人的四个方向为0，1，2，3对应NESW
    左转操作为：direct = (direct + 3) % 4
    右转操作为：direct = (direct + 1) % 4 
*/ 
const int maxn = 110;

struct Robot{
    int x, y, direct;
} robots[maxn];

struct Ops{
    int id, times;
    char action;
} ops[maxn];

void turn(int id, bool left){
    if (left)
        robots[id].direct = (robots[id].direct + 3) % 4;
    else 
        robots[id].direct = (robots[id].direct + 1) % 4;
}

void forward(int id){
    switch(robots[id].direct){
        case 0: robots[id].y++; break;
        case 1: robots[id].x++; break;
        case 2: robots[id].y--; break;
        case 3: robots[id].x--; break;   
    }
}

int judge(int id, int a, int b, int n){
    if (robots[id].x == 0 || robots[id].x == a + 1 || robots[id].y == 0 || robots[id].y == b + 1){
        return -1;
    }
    for (int i = 1; i <= n; i++){
        if (i == id) continue;
        if (robots[id].x == robots[i].x && robots[id].y == robots[i].y)
            return i;
    }
    return -2;
}

int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        int a, b, m, n;
        char direct;
        scanf("%d%d%d%d",&a,&b,&n,&m);
        for (int i = 1; i <= n; i++){
            scanf("%d%d %c", &robots[i].x, &robots[i].y, &direct);
            switch(direct){
                case 'N': robots[i].direct = 0; break;
                case 'E': robots[i].direct = 1; break;
                case 'S': robots[i].direct = 2; break;
                case 'W': robots[i].direct = 3; break;
            }
        }
//      printf("suc\n");
        for (int i = 0; i < m; i++){
            scanf("%d %c%d", &ops[i].id, &ops[i].action, &ops[i].times);
        }
        int i;
        for (i = 0; i < m; i++){
            bool flag = false;
            // 行动的次数，前进为前进的次数， 转圈需要模4 
            int step = (ops[i].action == 'F') ? ops[i].times : ops[i].times % 4;
            while (step --){
                switch(ops[i].action){
                    case 'L': turn(ops[i].id, true); break;
                    case 'R': turn(ops[i].id, false); break;
                    case 'F': forward(ops[i].id); break;
                }
                int res = judge(ops[i].id, a, b, n);
                if (res == -1){
                    printf("Robot %d crashes into the wall\n", ops[i].id);
                    flag = true;
                    break;
                }else if (res > 0){
                    printf("Robot %d crashes into robot %d\n", ops[i].id, res);
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (i == m){
            printf("OK\n");
        }
    }
} 

4. POJ1573——Robot Motion

4.1 题目描述

Description

<center> image

</center>

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are

N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)

For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.

Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.

You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.

Input

There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.

Output

For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before it is 1.

Sample Input
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

Sample Output

10 step(s) to exit
3 step(s) before a loop of 8 step(s)

4.2 解决思路

该问题的二维网格中定义了机器人前进的方向，它是一种典型的类似于走迷宫的问题，因此思路很直接，使用深度优先遍历，每次遍历计算当前的步数，并引入额外的数组存储当前位置的步数，出现循环的判断条件是当前步数不为0.

4.3 代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
/*
    二维数组行走问题的常用方法DFS，
    递归的边界是判断是否越界，
    如果存在循环，则使用一个额外数组判断  
*/

const int maxn = 10010;
char g[maxn][maxn];
int steps[maxn][maxn], step, bstep, cstep, m, n, start;  
bool flag;

void DFS(int x, int y, int s){
    if(x < 1 || x > m || y < 1 || y > n){ // 递归边界 
        flag = true;
        return ;
    }
    step = s;
//  printf("step:%d\n", s);
    // 如果未进入循环
    if (steps[x][y] == 0){
        steps[x][y] = s; //更新当前步数
        switch(g[x][y]){ // 深度遍历 
            case 'N': DFS(x - 1, y, s + 1); break;
            case 'S': DFS(x + 1, y, s + 1); break;
            case 'W': DFS(x, y - 1, s + 1); break;
            case 'E': DFS(x, y + 1, s + 1); break;
        } 
    }else{
        // 进入循环
        bstep = steps[x][y] - 1;
        cstep = s - steps[x][y]; 
    }
}

void output(int m, int n){
    for (int i = 1; i <= m; i++)
    {
        for(int j = 1;j <= n;j++){
            printf("%c", g[i][j]);
        }
        printf("\n");
     } 
}

int main(){
    while (~scanf("%d%d%d",&m, &n, &start) && m && n && start){
        flag = false;
        for(int i = 1; i <= m; i++){
            scanf("%s", g[i] + 1); // 注意从1下标开始存储
            fill(steps[i] + 1, steps[i] + 1 + n, 0); 
        }
//      output(m, n);
        DFS(1, start, 1);
        if (flag){
            printf("%d step(s) to exit\n", step);
        }else{
            printf("%d step(s) before a loop of %d step(s)\n", bstep, cstep);
        }
    }
} 

注意：

• 题目中的网格下标是从1开始，因此在初始化网格和步数数组时，需要从1开始初始化。
• 由于是一个cpp同时运行多个测试用例，在运行下一个测试用例时，所有定义的数据需要初始化，避免出现脏用。
• 进行DFS遍历时，如果记录DFS的中间结果，可添加全局变量。