[已解决]两只奶牛

柿子饼同学

题目 : https://www.luogu.com.cn/problem/P1518
(可以点题解) 这题目我过了 , 主要题解里有点看不懂 , 这个特征是什么鬼 , 为什么要这么算 , 有什么依据? 然后在什么样的题目中可以用起来?
下面有图 , 别走!!!
附上我的代码:

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. long long cow_face = 0, man_face = 0;
   
5. short dx[] = {-1, 0, 1, 0};
   
6. short dy[] = {0, 1, 0, -1};
   
7. short mx, my, cx, cy;
   
8. char mp[12][12];
   
9. int t = 0;
   
10. 
    
11. void movement(){
    
12.     if(mp[mx+dx[man_face%4]][my+dy[man_face%4]] == '*'){
    
13.         man_face++;
    
14.     }
    
15.     else{
    
16.         mx += dx[man_face%4];
    
17.         my += dy[man_face%4];
    
18.     }
    
19.     if(mp[cx+dx[cow_face%4]][cy+dy[cow_face%4]] == '*'){
    
20.         cow_face++;
    
21.     }
    
22.     else{
    
23.         cx += dx[cow_face%4];
    
24.         cy += dy[cow_face%4];
    
25.     }
    
26.     t++;
    
27. }
    
28. 
    
29. int main(){
    
30.     ios::sync_with_stdio(0);
    
31. 
    
32.     for(int i = 1; i <= 10; i++){
    
33.         for(int j = 1; j <= 10; j++){
    
34.             cin >> mp[i][j];
    
35.             if(mp[i][j] == 'F'){
    
36.                 mx = i; my = j;
    
37.             }
    
38.             if(mp[i][j] == 'C'){
    
39.                 cx = i; cy = j;
    
40.             }
    
41.         }
    
42.     }
    
43. 
    
44.     for(int i = 0; i < 12; i++){
    
45.         mp[0][i] = '*';
    
46.         mp[i][0] = '*';
    
47.         mp[11][i] = '*';
    
48.         mp[i][11] = '*';
    
49.     }
    
50.     int i = 0;
    
51.     while(mx != cx || my != cy){
    
52.         if(i > 202){ // 随便猜的一个最大值 , 没想到过了
    
53.             t = 0;
    
54.             break;
    
55.         }
    
56.         movement();  
    
57.         i++;  
    
58.     }
    
59. 
    
60.     cout << t << endl;
    
61. 
    
62.     return 0;
    
63. }

复制代码

谢谢解答~

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-6-25 21:46:38

以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另一个数组存储经过的路线，经过则 1 否则为 0，这样就不会重复路线了。
**以上只有一个未知路线，所以只需一个数组便可存入经过的路线。

同理，这题是牛和人的路线（有两条），假设人的路线为 A -> B -> C -> A，这里发现重复了 A 点，如果是用上述的方法，肯定就在这里结束代码吧？但是这样不够，因为虽然人的路线重复回去了 A 点，但牛可能已经和刚刚不同点了，比如：

人：A -> B -> C -> A
牛：B -> D -> E -> F

这里你会发现，人虽然回去 A 点（重复）但其结果不同，因为牛不是刚才那个地方，所以这次应该算不同的路线，这样问题来了，一共有多少种可能性呢？

所以用值替代：
比如 A 点，这里我就用 A(x, y) 代表它的位置，而人的坐标 x 以 1 为进制，y 以 10 为进制；牛 x 以 100 为进制，y 以 1000为进制，从上往下，从左往右，共 100 格。

例子：
假设 A 点为 (0, 0）、 B 点为 (0, 1）、 C 点为 (1, 1）、 D 点为 (1, 0）

人：A -> B -> C -> A
牛：C -> D -> A -> D

这时你会发现最后一步，人的路线重复了，但牛没有，代码如何实现（或知道有没有重复呢？）

人的起点值为 A(0, 0) 是 0*1 + 0*10 = 0 最后的 A 点一样是 0
牛的起点值为 C(1, 1) 是 1*100 + 1*1000 = 1100 最后的点是 D(1, 0) 值是 1*100 + 0*1000 = 100

起点值：0 + 1100 = 1100
最后的点值：0 + 100 = 100
1100 和 100 不相同，所以可以判断这种状况的路线之前没有走过。

这题的题解：有关权值知识。在数学领域，权值指加权平均数中的每个数的频数，也称为权数或权重。

跳转到最佳答案楼层

想入门的新人

这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就没有进入死循环，如果相同那就可以结束返回追不到就ok了

想入门的新人

想入门的新人 发表于 2022-6-25 21:27
这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就 ...

这个bool数组zt[tdz]未初始化，如何才为true或flase

傻眼貓咪

以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另一个数组存储经过的路线，经过则 1 否则为 0，这样就不会重复路线了。
**以上只有一个未知路线，所以只需一个数组便可存入经过的路线。

同理，这题是牛和人的路线（有两条），假设人的路线为 A -> B -> C -> A，这里发现重复了 A 点，如果是用上述的方法，肯定就在这里结束代码吧？但是这样不够，因为虽然人的路线重复回去了 A 点，但牛可能已经和刚刚不同点了，比如：

人：A -> B -> C -> A
牛：B -> D -> E -> F

这里你会发现，人虽然回去 A 点（重复）但其结果不同，因为牛不是刚才那个地方，所以这次应该算不同的路线，这样问题来了，一共有多少种可能性呢？

所以用值替代：
比如 A 点，这里我就用 A(x, y) 代表它的位置，而人的坐标 x 以 1 为进制，y 以 10 为进制；牛 x 以 100 为进制，y 以 1000为进制，从上往下，从左往右，共 100 格。

例子：
假设 A 点为 (0, 0）、 B 点为 (0, 1）、 C 点为 (1, 1）、 D 点为 (1, 0）

人：A -> B -> C -> A
牛：C -> D -> A -> D

这时你会发现最后一步，人的路线重复了，但牛没有，代码如何实现（或知道有没有重复呢？）

人的起点值为 A(0, 0) 是 0*1 + 0*10 = 0 最后的 A 点一样是 0
牛的起点值为 C(1, 1) 是 1*100 + 1*1000 = 1100 最后的点是 D(1, 0) 值是 1*100 + 0*1000 = 100

起点值：0 + 1100 = 1100
最后的点值：0 + 100 = 100
1100 和 100 不相同，所以可以判断这种状况的路线之前没有走过。

这题的题解：有关权值知识。在数学领域，权值指加权平均数中的每个数的频数，也称为权数或权重。

ExiaGN001

终于在鱼C找到一个OIer了...哭死

柿子饼同学

想入门的新人 发表于 2022-6-25 21:27
这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就 ...

嗯嗯 , 谢谢回答

jhq999

看看是否各自同时路过相同的点相同的方向，是就是死循环。永远不会相遇。
感觉可以用结构体
看经农夫以一个方向过某一点，牛肯定在100个点里的位置和方向里的某一个，

1. struct FPOINT
   
2. {
   
3.         BOOL c[10][10][3];
   
4. };
   
5. FPOINT f[10][10][3]={0};
   
6. 然后
   
7. if(f[fx][fy][fdt].c[cx][cy][cdt])return;////////cdt牛的方向 fdt农夫的方向
   
8. f[fx][fy][fdt].c[cx][cy][cdt]=1;

复制代码

不知道这个想法有漏洞没有？

柿子饼同学

ExiaGN001 发表于 2022-6-26 07:25
终于在鱼C找到一个OIer了...哭死

啊 , 在搞今年普及组
我太弱了

柿子饼同学

傻眼貓咪 发表于 2022-6-25 21:46
以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另 ...

就是一个状态有三个值 : 坐标 x , 坐标 y , 朝向
这里给每个坐标, 朝向乘以不同的数 , 便于区分不同状态 ?
然后这样省空间?

傻眼貓咪

柿子饼同学 发表于 2022-6-26 13:40
就是一个状态有三个值 : 坐标 x , 坐标 y , 朝向
这里给每个坐标, 朝向乘以不同的数 , 便于区分不同状 ...

没错

柿子饼同学

傻眼貓咪 发表于 2022-6-26 13:45
没错

哦哦哦就是每个状态相当于有一个唯一的 "码"
这样不用开结构体了

柿子饼同学

jhq999 发表于 2022-6-26 11:39
看看是否各自同时路过相同的点相同的方向，是就是死循环。永远不会相遇。
感觉可以用结构体
看经农夫以一 ...

好像是可以的 , 反正总的来说就是每一个状态要有区分
谢谢解答

柿子饼同学

想入门的新人 发表于 2022-6-25 21:37
这个bool数组zt[tdz]未初始化，如何才为true或flase

唔,  前面有初始化的

傻眼貓咪

柿子饼同学 发表于 2022-6-26 13:50
哦哦哦就是每个状态相当于有一个唯一的 "码"
这样不用开结构体了

是啊，很多大佬都是用这种方法的。

柿子饼同学

傻眼貓咪 发表于 2022-6-26 13:53
是啊，很多大佬都是用这种方法的。

厉害

jhq999

有简单的算法吗？如果1000*1000怎么办？恐怖的上T

ExiaGN001

柿子饼同学 发表于 2022-6-26 13:31
啊 , 在搞今年普及组
我太弱了

我山东大连的（大嘘
（大连其实是辽宁的）
去年普及省二，提高靠T3无解输出-1骗来16分

想入门的新人

傻眼貓咪 发表于 2022-6-25 21:46
以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另 ...

上面还考虑了方向，这里不用考虑方向吗？ 我认为上面应该只需要考虑牛的方向，因为人的方向和牛一样

柿子饼同学

想入门的新人 发表于 2022-6-26 14:51
上面还考虑了方向，这里不用考虑方向吗？ 我认为上面应该只需要考虑牛的方向，因为人的方向和牛一样

不一定 , 因为障碍物不同 , 比如人前面有障碍 , 必须转向
而牛没有 , 所以不用

柿子饼同学

ExiaGN001 发表于 2022-6-26 14:36
我山东大连的（大嘘
（大连其实是辽宁的）
去年普及省二，提高靠T3无解输出-1骗来16分

唔
我江苏的
目前还挺弱
过了暑假就去考了