网门网站下载地址,188自助建站系统,网站专题页ps教程,东城免费做网站P4009 汽车加油行驶问题 紫题#xff0c;但是DFS。
思路
记忆化搜索#xff0c;分多钟情况去搜索。 注意该题不用标记#xff0c;有可能会往回走。 有可能这样走。
代码
#includebits/stdc.h
#includecstring
#includequeue
#includeset但是DFS。
思路
记忆化搜索分多钟情况去搜索。 注意该题不用标记有可能会往回走。 有可能这样走。
代码
#includebits/stdc.h
#includecstring
#includequeue
#includeset
#includestack
#includevector
#includemap
#define ll long long
#define lhs printf(\n);
using namespace std;
const int N1e510;
const int M2024;
const int inf0x3f3f3f3f;
ll n,a,b,c,d,k;
ll g[114][114];
ll ansinf;
int dx[]{1,0,0,-1};
int dy[]{0,1,-1,0};
ll vis[114][114];
ll v[114][114][20];
int mp[114][114];
int flag;
/*
x,y当前位置
num剩余步数
step总花费*/void dfs(ll x,ll y,ll num,ll step)
{if(xn and yn)//找到答案{ansmin(ans,step);return;}if(v[x][y][num]step)return;//记忆化v[x][y][num]step;if(stepans)return;for(int i0;i4;i){int l0;int nxxdx[i];int nyydy[i];if(i3 or i2)//往回走的话就要b{lb;}if(nx1 and nxn and ny1 and nyn and vis[nx][ny]0 and num1){
// vis[nx][ny]1;
// 这里不用标记因为有可能往回走if(g[nx][ny]0 and num1)//不是加油站但是没油了{//建一个加油站并加油g[nx][ny]1;dfs(nx,ny,k,stepcal);g[nx][ny]0;//按理来说是走不了但是万一下一步是终点呢大不了就是退回来dfs(nx,ny,num-1,stepl);}else if(g[nx][ny]1)//加油站必须加油{dfs(nx,ny,k,stepal);}else if(g[nx][ny]0 and num!1)//剩余情况就直接走{dfs(nx,ny,num-1,stepl);}
// vis[nx][ny]0;}}
}
int main()
{memset(v,inf,sizeof v);cinnkabc;for(int i1;in;i){for(int j1;jn;j){cing[i][j];}} dfs(1,1,k,0);coutans;return 0;
}AC记录
