[已解决]两只奶牛

柿子饼同学

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

#include <bits/stdc++.h>
using namespace std;

long long cow_face = 0, man_face = 0;
short dx[] = {-1, 0, 1, 0};
short dy[] = {0, 1, 0, -1};
short mx, my, cx, cy;
char mp[12][12];
int t = 0;

void movement(){
    if(mp[mx+dx[man_face%4]][my+dy[man_face%4]] == '*'){
        man_face++;
    }
    else{
        mx += dx[man_face%4];
        my += dy[man_face%4];
    }
    if(mp[cx+dx[cow_face%4]][cy+dy[cow_face%4]] == '*'){
        cow_face++;
    }
    else{
        cx += dx[cow_face%4];
        cy += dy[cow_face%4];
    }
    t++;
}

int main(){
    ios::sync_with_stdio(0);

    for(int i = 1; i <= 10; i++){
        for(int j = 1; j <= 10; j++){
            cin >> mp[i][j];
            if(mp[i][j] == 'F'){
                mx = i; my = j;
            } 
            if(mp[i][j] == 'C'){
                cx = i; cy = j;
            }
        }
    }

    for(int i = 0; i < 12; i++){
        mp[0][i] = '*';
        mp[i][0] = '*';
        mp[11][i] = '*';
        mp[i][11] = '*';
    }
    int i = 0;
    while(mx != cx || my != cy){
        if(i > 202){ // 随便猜的一个最大值 , 没想到过了
            t = 0;
            break;
        }
        movement();  
        i++;  
    }

    cout << t << endl;

    return 0;
}

谢谢解答~

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

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个点里的位置和方向里的某一个，

struct FPOINT
{
        BOOL c[10][10][3];
};
FPOINT f[10][10][3]={0};
然后
if(f[fx][fy][fdt].c[cx][cy][cdt])return;////////cdt牛的方向 fdt农夫的方向
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分

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