[题解]|[题解] 迷宫搜索再加强版 C++
文章目录
- Description
- Input
- Output
- Sample Input
- Sample Output
- 思路
#题目
迷宫搜索再加强版
Description 正所谓,“怕什么真理无穷,进一寸,有一寸的欢喜”
现在你已不满足于判断一个点能否走到另一个点了。
你希望知道从一个点到另一个点,用T秒的时间有多少种方式。
Input 第1行: 3个用空格隔开的整数:N,M,T
第2…N+1行: 第i+1行为M个连续的字符,描述了迷宫第i行各点的情况,
保证字符是’.‘和’‘中的一个,’.‘表示可通过的点,’'表示不可走的点
第N+2行: 4个用空格隔开的整数:R1,C1,R2,以及C2
Output
- 第1行: 输出S,含义如题中所述
4 5 6
…*.
…*.
…
…
1 3 1 5
Sample Output
1
//用6秒从(1,3)走到(1,5)的方法只有一种
思路 【[题解]|[题解] 迷宫搜索再加强版 C++】bfs跑完开三维数组i,j,k代表在坐标i,j第k时的方案数,每次拓展时dp[i][j][k]加当前状态的个数
每当now.d>t时就跳过
最后输出dp[ex][ey][k]也就是第k时到终点的 个数
#include
using namespace std;
int n,m,t,cnt;
int ex,ey;
string maze[1010];
bool in(int x,int y){
return x>=0 && y>=0 && x q;
q.push(node(sx,sy,0));
while(!q.empty()){
node now=q.front();
//q.pop();
if(now.d>t){
continue;
}
for(int i=0;
i<4;
i++){
int tx=now.x+dir[i][0];
int ty=now.y+dir[i][1];
if(in(tx,ty) && maze[tx][ty]!='*'){
dp[tx][ty][now.d+1]+=dp[now.x][now.y][now.d];
if(dp[tx][ty][now.d+1]-dp[now.x][now.y][now.d]>0){
continue;
}
q.push(node(tx,ty,now.d+1));
}
}
}
return dp[ex][ey][t];
}
int main(){
int sx,sy;
cin>>n>>m>>t;
for(int i=0;
i>maze[i];
}
while(1);
cin>>sx>>sy>>ex>>ey;
sx--;
sy--;
ex--;
ey--;
dp[sx][sy][0]=1;
cout<
推荐阅读
- 【译】20个更有效地使用谷歌搜索的技巧
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- locate搜索
- springboot结合redis实现搜索栏热搜功能及文字过滤
- 茶事|茶事 | 单丛里的一泡奇葩
- Pytorch学习|sklearn-SVM 模型保存、交叉验证与网格搜索
- 销量搜索
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- 17个搜索引擎
- 搜索引擎有哪些