小题笔记——农夫找牛c/c++

keyword：
模拟
特征值

题意：

农夫需要在一张10*10的地图里抓牛。农夫和牛的移动规则相同：每次朝着原来的方向前进一格；如果前方是障碍物或者地图边界，那么本次顺时针旋转90°。初始方向向上。计算并输出农夫需要多少步才能抓到牛（二者在同一格相遇），永远不相遇则输出0

•保证地图中只有一个F和一个C，且F和C一开始不会在同一个格子里
•如果农夫和牛在移动时穿过对方，但没有在同一格相遇，我们不认为他们相遇了

题意解释图

思路：

  1. 本题是一道典型的模拟题（也是常见的地图题），是很常见的用结构体记录横纵坐标以及下一步方向的方法。但是本来不会啊qaq所以还是要记下来

    • 注：通常以第一个点为原点，向右向下建立坐标轴

  2. 由于牛和农夫行走方式相同，写一个子函数实现行走/遇到障碍物转向的功能，传递结构体，返回值也是结构体

  3. 本题的特殊点在于如何判断永远不会相遇：

    • 不会相遇的情况：农夫在A(x1,y1)(x_1,y_1)，方向d1，牛在B(x2,y2)(x_2,y_2)，方向d2，而之前出现过一个时刻与这情况完全相同
    • 模拟方法：用特征值记录: 这里一共有六个值要记录，且均为个位数，则合在一起是一个六位数。如A(1,2) , d1=0, B(3,4), d2=1， 则special=120341。知道每个位数是多少，乘10的具体倍数就能得到special了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <bits/stdc++.h>

using namespace std;

struct Data

{

    int x;

    int y;

    int d; //朝向，0~3：上右下左（顺时针）

} farmer, cow;

//地图是以向右为x轴正方向，向下为y轴正方向

char g[15][15];     // 地图grid

bool book[1000010]; //标记特征值

  

struct Data fun(struct Data p) //处理转向

{

    if (p.d == 0)

    {

        if (p.y - 1 > 0 && g[p.y - 1][p.x] != '*')//注意是>不是>=

            p.y--;

        else

            p.d = 1;

    }

    else if (p.d == 1)

    {

        if (p.x + 1 <= 10 && g[p.y][p.x + 1] != '*')

            p.x++;

        else

            p.d = 2;

    }

    else if (p.d == 2)

    {

        if (p.y + 1 <= 10 && g[p.y + 1][p.x] != '*')

            p.y++;

        else

            p.d = 3;

    }

    else if (p.d == 3)

    {

        if (p.x - 1 > 0 && g[p.y][p.x - 1] != '*')

            p.x--;

        else

            p.d = 0;

    }

    return p;

}

  

int main()

{

    bool flag = false;

    int cnt = 0;

    for (int i = 1; i <= 10; i++)//读入初始位置是（1,1）

    {

        scanf("%s", g[i] + 1); // 读入字符串，从下标1开始读入,按行迭代

        for (int j = 1; j <= 10; j++)

        {

            if (g[i][j] == 'F')

                farmer = {j, i, 0}; //写入结构体

            if (g[i][j] == 'C')

                cow = {j, i, 0};

        }

    }

    while (1)

    {

        if (farmer.x == cow.x && farmer.y == cow.y)

        {

            flag = true;

            break;

        }

  

        int special; //特征值

        special = (farmer.x - 1) + (farmer.y - 1) * 10 + farmer.d * 100 + (cow.x - 1) * 1000 + (cow.y - 1) * 10000 + cow.d * 100000;
        //减去1的原因是我们地图是从1开始录入的，而最大横/纵坐标为10就是两位数了。
        //减1保证是个位数，且不影响特征值特征性

        if (book[special])

            break;

        else

            book[special] = true;

  

        farmer = fun(farmer);

        cow = fun(cow);

        cnt++;

    }

    if (flag)

        printf("%d", cnt);

    else

        printf("0\n");

    return 0;

}

小结

  1. 在地图的细节处容易出错
  2. 学习了特征值在模拟中的作用
#小题笔记
小题笔记——农夫找牛c/c++
http://sample.com/2022/04/22/农夫找牛/
作者
LuoYutong
发布于
2022年4月22日
许可协议