[题解]|[题解] 迷宫搜索再加强版 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,含义如题中所述
Sample Input
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<

    推荐阅读