旅行者的大逃脱
时间限制：2秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
旅行者偷走了芙宁娜最爱的甜点。此时，芙宁娜正在由n nn行m mm列方格组成的枫丹国内内四处搜捕他。方格以从上到下1 , 2 , … , n 1,2,…,n1,2,…,n行、从左到右1 , 2 , … , m 1,2,…,m1,2,…,m列编号。初始时刻为1 11，旅行者位于左上角格子( 1 , 1 ) (1,1)(1,1)，他的目标是在大门关闭前到达右下角格子( n , m ) (n,m)(n,m)从而逃离枫丹国。旅行者的移动规则如下：
∙ ∙在每一个时刻，他只能沿向下或向右选择一个方向移动，并可以一次前进任意正整数步；移动完成后，时刻加1 11。
芙宁娜派出了q qq名检查官，第i ii名检查官将在时刻t i t_iti占据格子( x i , y i ) (x_i,y_i)(xi,yi)并一直驻守。无论旅行者在时刻τ ( τ ≧ t i ) τ (τ≧t_i)τ(τ≧ti)：
- 到达该格子；
- 经过该格子；
- 离开该格子，
他都会立即被捕获，从而导致逃脱失败。此外，在时刻k kk之后大门将被永久关闭，若旅行者到达( n , m ) (n,m)(n,m)时时刻已经大于k kk，则同样逃脱失败。
请你帮助旅行者计算：
1. 在所有合法方案中逃离所需的最短时间；
2. 在模998 244 353 998 244 353998 244 353意义下，可以逃脱的总方案数量。
输入描述：
本题包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 5 ) T(1≦T≦5)T(1≦T≦5)代表数据组数，每组测试数据描述如下：
- 一行四个整数n , m , q , k ( 2 ≦ n , m ≦ 500 ; 1 ≦ q ≦ 100 ; 1 ≦ k ≦ 100 ) n,m,q,k(2≦n,m≦500; 1≦q≦100; 1≦k≦100)n,m,q,k(2≦n,m≦500;1≦q≦100;1≦k≦100)；
- 此后q qq行，第i ii行输入三个整数x i , y i , t i ( 1 ≦ x i ≦ n ; 1 ≦ y i ≦ m ; 1 ≦ t i ≦ k ) x_i,y_i,t_i(1≦x_i≦n; 1≦y_i≦m; 1≦t_i≦k)xi,yi,ti(1≦xi≦n;1≦yi≦m;1≦ti≦k)――第i ii名检查官的坐标及出现时刻。
此外，数据保证( 1 , 1 ) (1,1)(1,1)和( n , m ) (n,m)(n,m)两格不会有检查官出现，但是可能会出现很多检察官出现在同一个格子的情况。
输出描述：
对于每组测试数据：
- 若T r a v e l e r TravelerTraveler无论如何都无法逃脱，输出一行− 1 -1−1；
- 否则输出两个整数，依次为方案数量（对998 244 353 998 244 353998 244 353取模）与最短时间。
示例1
输入：
2 2 3 2 5 1 3 1 2 2 3 2 3 2 5 1 3 1 2 2 2输出：
1 2 -1说明：
约定：我们用 TT 来代表旅行者的位置，数字代表对应时刻会出现的检察官，F FF代表右下角的大门。
在第一个样例中，最短时间为2 22，且仅存在一条合法路径（先向下再向右再向右）。
在第二个样例中，旅行者必被捕获，故输出− 1 -1−1。
示例2
输入：
1 8 8 11 8 7 4 2 3 1 2 1 8 1 2 1 1 5 4 1 5 8 3 8 5 4 7 1 1 3 6 1 7 2 1 1 7 2输出：
7763 3解题思路
本题核心是三维动态规划+前缀和优化，结合检察官障碍规则求解最短逃脱时间与方案数。定义dp[i][j][t]表示第t时刻到达坐标(i,j)的合法方案数，初始化起点dp[1][1][1]=1。利用旅行者每时刻可沿单方向走任意步的规则，通过行、列前缀和优化D P DPDP转移，规避暴力枚举步数的低效问题。预处理每个格子的最早检察官驻守时刻，若当前时刻超过该值则清空对应状态，排除非法路径。遍历所有合法时刻（ ≤ k ） （≤k）（≤k），统计终点的总方案数，记录最早到达终点的时刻为最短时间，无合法方案则输出-1。
总结
核心逻辑：用三维DP维护时刻-位置的方案数，前缀和优化移动转移，过滤检察官障碍的非法路径。
关键操作：D P DPDP状态初始化、前缀和优化转移、障碍时刻预处理、最短时间与总方案数统计。
效率保障：前缀和将转移复杂度优化至线性，完美适配n,m≤500、k≤100的数据规模。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e5+10;constll INF=1e18;constll M=1e6+10;constll mod=998244353;ll dp[510][510][110];voidsolve(){ll n,m,q,k,op=-1,ans=0;cin>>n>>m>>q>>k;vvtvvl(n+3,vector<ll>(m+3,2e18));for(ll i=1,x,y,t;i<=q;i++){cin>>x>>y>>t;vvl[x][y]=min(vvl[x][y],t);}dp[1][1][1]=1;for(ll kk=2;kk<=k+1;kk++){vector<ll>vl(m+10);for(ll i=1;i<=n;i++){ll sum=0;for(ll j=1;j<=m;j++){dp[i][j][kk]=(sum+vl[j])%mod;sum=(sum+dp[i][j][kk-1])%mod;vl[j]=(vl[j]+dp[i][j][kk-1])%mod;if(kk>vvl[i][j])sum=0,vl[j]=0;}}ans=(ans+dp[n][m][kk])%mod;if(dp[n][m][kk]!=0&&op==-1)op=kk;}if(op==-1)cout<<-1<<endl;elsecout<<ans<<" "<<op-1<<endl;}intmain(){ll t=1;cin>>t;while(t--)solve();return0;}
