两只奶牛
本帖最后由 柿子饼同学 于 2022-6-25 20:15 编辑题目 : 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;
int t = 0;
void movement(){
if(mp]] == '*'){
man_face++;
}
else{
mx += dx;
my += dy;
}
if(mp]] == '*'){
cow_face++;
}
else{
cx += dx;
cy += dy;
}
t++;
}
int main(){
ios::sync_with_stdio(0);
for(int i = 1; i <= 10; i++){
for(int j = 1; j <= 10; j++){
cin >> mp;
if(mp == 'F'){
mx = i; my = j;
}
if(mp == 'C'){
cx = i; cy = j;
}
}
}
for(int i = 0; i < 12; i++){
mp = '*';
mp = '*';
mp = '*';
mp = '*';
}
int i = 0;
while(mx != cx || my != cy){
if(i > 202){ // 随便猜的一个最大值 , 没想到过了
t = 0;
break;
}
movement();
i++;
}
cout << t << endl;
return 0;
}
谢谢解答~ 这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就没有进入死循环，如果相同那就可以结束返回追不到就ok了
想入门的新人 发表于 2022-6-25 21:27
这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就 ...
这个bool数组zt未初始化，如何才为true或flase 本帖最后由 傻眼貓咪 于 2022-6-25 21:52 编辑
以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另一个数组存储经过的路线，经过则 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 不相同，所以可以判断这种状况的路线之前没有走过。
这题的题解：有关权值知识。在数学领域，权值指加权平均数中的每个数的频数，也称为权数或权重。
终于在鱼C找到一个OIer了...哭死 想入门的新人 发表于 2022-6-25 21:27
这个特征值看不懂，但是他说做标记，我认为只要保存人和牛每次走后的坐标和方向，只要和以前对比没有相同就 ...
嗯嗯 , 谢谢回答 本帖最后由 jhq999 于 2022-6-26 11:55 编辑
看看是否各自同时路过相同的点相同的方向，是就是死循环。永远不会相遇。
感觉可以用结构体
看经农夫以一个方向过某一点，牛肯定在100个点里的位置和方向里的某一个，
struct FPOINT
{
BOOL c;
};
FPOINT f={0};
然后
if(f.c)return;////////cdt牛的方向 fdt农夫的方向
f.c=1;
不知道这个想法有漏洞没有？ ExiaGN001 发表于 2022-6-26 07:25
终于在鱼C找到一个OIer了...哭死
啊 , 在搞今年普及组
我太弱了 本帖最后由 柿子饼同学 于 2022-6-26 13:49 编辑
傻眼貓咪 发表于 2022-6-25 21:46
以迷宫为例子，找出从起点到终点的路线，为了预防无限循环路线，必须另外储存每次经过的路线，比如：创建另 ...
就是一个状态有三个值 : 坐标 x , 坐标 y , 朝向
这里给每个坐标, 朝向乘以不同的数 , 便于区分不同状态 ?
然后这样省空间? 柿子饼同学 发表于 2022-6-26 13:40
就是一个状态有三个值 : 坐标 x , 坐标 y , 朝向
这里给每个坐标, 朝向乘以不同的数 , 便于区分不同状 ...
没错{:5_105:} 傻眼貓咪 发表于 2022-6-26 13:45
没错
哦哦哦就是每个状态相当于有一个唯一的 "码"
这样不用开结构体了 jhq999 发表于 2022-6-26 11:39
看看是否各自同时路过相同的点相同的方向，是就是死循环。永远不会相遇。
感觉可以用结构体
看经农夫以一 ...
好像是可以的 , 反正总的来说就是每一个状态要有区分
谢谢解答 想入门的新人 发表于 2022-6-25 21:37
这个bool数组zt未初始化，如何才为true或flase
唔,前面有初始化的 柿子饼同学 发表于 2022-6-26 13:50
哦哦哦就是每个状态相当于有一个唯一的 "码"
这样不用开结构体了
是啊，很多大佬都是用这种方法的。{:5_106:} 傻眼貓咪 发表于 2022-6-26 13:53
是啊，很多大佬都是用这种方法的。
厉害 本帖最后由 jhq999 于 2022-6-26 14:05 编辑
有简单的算法吗？如果1000*1000怎么办？恐怖的上T{:5_107:} 柿子饼同学 发表于 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分
唔
我江苏的
目前还挺弱
过了暑假就去考了
页:
[1]
2