第一眼:DFS秒了
第二眼:坏了这是数学
by _TCR_ @ 2024-03-21 18:24:27
设走x次(+3,+4),y次(+4,+3),p次(+5,0),q次(0,+5),然后解方程组,得到一个7(x+y)+5(p+q)=66,然后感觉可以exgcd求一组解
by long_ting @ 2024-03-21 18:57:02
```cpp
#include<bits/stdc++.h>
#define mkp make_pair
using namespace std;
int fx[]={0,3,3,-3,-3,4,4,-4,-4,5,-5,0,0};
int fy[]={0,4,-4,4,-4,-3,3,3,-3,0,0,5,-5};
int ex,ey,st;
int s[100][100];
int main()
{
cin>>ex>>ey;
queue<pair<int,int> >q;
q.push(mkp(0,0));
s[0][0]=1;
while(1)
{
int x=q.front().first,y=q.front().second;
q.pop();
cout<<x<<" "<<y<<endl;
if(x==ex&&y==ey)
{
cout<<s[ex][ey]-1;
return 0;
}
for(int i=1;i<=12;i++)
{
int _x=x+fx[i],_y=y+fy[i];
if(_x<0||_y<0)continue;
if(!s[_x][_y])
{
s[_x][_y]=s[x][y]+1;
q.push(mkp(_x,_y));
}
}
}
return 0;
}
```
跑出来是10
by zwxadz @ 2024-03-21 19:33:21
@[long_ting](/user/1134329) @[zwxadz](/user/694647) 感谢,关了。
但是这是数学题(恼)我总不能在考场上整dfs罢(
by _TCR_ @ 2024-03-21 20:09:58
@[zwxadz](/user/694647) 看错力是bfs
by _TCR_ @ 2024-03-21 20:13:38
@[_TCR_](/user/483466) 蹲个答案,顺便好奇一下您的年级?
by 流泪的小酒窝 @ 2024-03-21 21:40:23
@[流泪的小酒窝](/user/540979) 10
高一物理类
by _TCR_ @ 2024-03-21 21:41:49
@[_TCR_](/user/483466) (完了,知识点不够)你可以考虑给出一种答案然后证明不可能有更小的答案?
by 流泪的小酒窝 @ 2024-03-21 21:43:45
@[_TCR_](/user/483466) 会了,首先答案是10,你自己构造一个,然后因为总共x+y=66,一次最多移动7,所以最小值>=66/7上取整,上取整=10
by 流泪的小酒窝 @ 2024-03-21 22:01:32
@[流泪的小酒窝](/user/540979) 这个似乎是向量题,真的不知道考的啥知识点
by _TCR_ @ 2024-03-21 22:17:27