rt，蒟蒻基本只会暴搜，写了BFS后只能拿30pts，剩下的都MLE了

但是由于只剩一周时间，恶补动规时间稍紧，希望有佬提供部分分优化策略，感激不尽

提交记录

//原来可以买很多火车票。。。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

//ifstream cin("travel2.in");

struct node{
    int x,y;
    ll a,b;
    ll ap=0,bp=0;
    ll money=0;
};
node graph[50][50];

int n,m,k;

void input(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> graph[i][j].a;
            graph[i][j].x=i;
            graph[i][j].y=j;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin >> graph[i][j].b;
    }
}

void bfs(){
    queue<node> q;
    ll plan[50][50]={0};

    graph[1][1].money=k;
    q.push(graph[1][1]);

    while(!q.empty()){
        node now=q.front();
        int i=now.x,j=now.y;

        ll ap=now.ap,bp=now.bp;
        ll a=now.a,b=now.b;
        ll money=now.money;

//        if((j==1||j==2)&&(i==1||i==2))
//            printf("%d %d %ld %ld %ld %ld %ld\n",i,j,ap,bp,money,now.a,now.b);
        if(money==0&&ap==0&&bp==0){
            plan[i][j]++;
            q.pop();
            continue;
        }

        //buy a&b
        for(ll am=0,sm=money;sm>=0;++am,sm=money-am*a){
            for(ll bm=0;sm>=0;++bm,sm-=b){
                //ap:(i+1,j)
                if(ap+am-1>=0&&i+1<=n){
                    node nd=graph[i+1][j];
                    nd.ap=ap+am-1;nd.bp=bp+bm;
                    nd.money=sm;
                    q.push(nd);
                }
                //bp:(i,j+1)
                if(bp+bm-1>=0&&j+1<=m){
                    node nd=graph[i][j+1];
                    nd.bp=bp+bm-1;nd.ap=ap+am;
                    nd.money=sm;
                    q.push(nd);
                }
            }
        }
        q.pop();
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout << plan[i][j]%998244353 << ' ';
        }
        cout << '\n';
    }

    return ;
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> m >> k;
    input();
    bfs();

    return 0;
}