iis7.5配置网站,建筑设计说明万能模板,给别的公司提供网站建设,荣成市城乡建设局网站搜索不知道为什么没有人写bfs觉得挺像是标准个bfs的 状态因为要统计次数#xff0c;不能简单地跳过一个被经过的点这样的话#xff0c;状态量会爆炸采用记忆化设dp[i][j][k]表示在第k分钟到达点(i,j)的方案数以地点时间作为状态避免同一状态被反复拓展这样#xff0c;状态量…搜索不知道为什么没有人写bfs觉得挺像是标准个bfs的 状态因为要统计次数不能简单地跳过一个被经过的点这样的话状态量会爆炸采用记忆化设dp[i][j][k]表示在第k分钟到达点(i,j)的方案数以地点时间作为状态避免同一状态被反复拓展这样状态量将减少至最多100*100*15 转移这就比较显然了对于将被拓展的状态在计数时加上当前状态的方案数如果这个状态曾被拓展就不要别的操作了否则将这一状态入队预备拓展其他状态 代码是这样的 #includeiostream
#includecstdio
#includequeue
using namespace std;
struct node{int x,y,s; //x、y表示坐标s表示时间
};
queuenodeq;
int n,m,t,r1,c1,r2,c2,dp[110][110][20];
int dx[4]{0,0,1,-1};
int dy[4]{1,-1,0,0}; //移动
string s[110];
int main()
{cinnmt;for(int i1;in;i)cins[i];cinr1c1r2c2;dp[r1][c1][0]1; //初始方案数为1q.push(node{r1,c1,0});while(!q.empty()){node uq.front();q.pop();for(int i0;i4;i){node th;th.xu.xdx[i];th.yu.ydy[i];th.su.s1;if(dp[th.x][th.y][th.s]){dp[th.x][th.y][th.s]dp[u.x][u.y][u.s];continue; //当前状态曾被拓展}if(th.x1||th.xn||th.y1||th.ym||s[th.x][th.y-1]*||th.st)continue; //越界或不能走或超时跳过dp[th.x][th.y][th.s]dp[u.x][u.y][u.s]; //计数q.push(th);}}coutdp[r2][c2][t]endl;return 0;
} 转载于:https://www.cnblogs.com/ivanovcraft/p/9160658.html
