0
已解决
初级启示者
对于这道很奇怪的题目，我有2种思路：
1. 广搜（bfs），因为它比深搜效率高，所以它在模拟里基本上是最佳的方案
2. 总结归纳，推导结论，由于输入只有两个数字，我们要使得这2个数字的计算结果为一个值
方案1的实施，不知道为什么编译错误
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
struct node{
ll x,y;
};
map<node,bool> num;
map<node,ll> road;
ll n,m,dir[5][2]={{0,1},{1,0},{-1,0},{0,-1}};
queue<node> q;
void bfs()
{
q.push((node){1,1});
num[(node){1,1}]=true;
road[(node){1,1}]=1;
while(!q.empty())
{
node h=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll nextx=h.x+dir[i][0],nexty=h.y+dir[i][1];
if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m&&!num[(node){nextx,nexty}])
{
road[(node){nextx,nexty}]+=road[(node){h.x,h.y}];
num[(node){nextx,nexty}]=true;
q.push((node){nextx,nexty});
}
}
}
}
int main()
{
cin>>n>>m;
bfs();
cout<<road[(node){n,m}];
}大家帮忙看看这道题啊
0
已采纳
初级天翼
map内部自动排序，确实需要重载！
0
初级启示者
编译显示
然而我并没有对node类型的元素进行比较，难不成我要多余重载一个运算符？
0
初级启示者
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
struct node{
ll x,y;
bool operator< (const node &tmp)const{
return x<tmp.x;
}
};
map<node,bool> num;
map<node,ll> road;
ll n,m,dir[5][2]={{0,1},{1,0},{-1,0},{0,-1}};
queue<node> q;
inline void bfs()
{
q.push((node){1,1});
num[(node){1,1}]=true;
road[(node){1,1}]=1;
while(!q.empty())
{
node h=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll nextx=h.x+dir[i][0],nexty=h.y+dir[i][1];
if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m&&!num[(node){nextx,nexty}])
{
road[(node){nextx,nexty}]+=road[(node){h.x,h.y}];
num[(node){nextx,nexty}]=true;
q.push((node){nextx,nexty});
}
}
}
}
int main()
{
cin>>n>>m;
bfs();
cout<<road[(node){n,m}];
}
加了一个operator重载运算符，但是结果样例输出1？？？？？
赵逸凡在2020-08-31 17:45:20追加了内容
我的思路：从起点出发，向四周寻找路径，对于由起点出发的一个点，它的状态必定是由这个起点的状态推导过来的，因为我在每个点用map做了是否走过的标记，如果到这个起点路径经过了这个点，因为我的程序不允许走回头路，所以不会由此更新这个点的状态，但这样存在一种问题，这个起点的状态所包含的路径可能有些没有经过这个点，所以有些有效的状态应该没有及时传送入这个点的状态，所以求助我该怎么办？再存一个4*1e9的大数组来记录路径，然后用近似O(n²m²)的复杂度来求解？
0
缔造者
1
