ar采蘑菇

D-ar采蘑菇
题意：
起点在(0,0),目标在(n,m),指定k种行走方案。问走到终点最多能使用多少种方案。

思路：
范围很小，可以搜索也可以状压dp。
只用了状压的做法。
dp[i][j][k] 表示走到i，j，可以用q种行走方式走到(k是这q种行走方式的二进制串)
枚举每一点的每一种状态，考虑从前面哪个状态转移过来即可，注意当前到达该点的行走方式可能前面用过也可能还没用过。

坑点:这是笛卡尔坐标系，起点在左下角，即R是向右走，应该是x++。而不是正常碰到起点在左上角，右走是y++，

#include<bits/stdc++.h>
using namespace std;
int dx[15],dy[15];
int dp[105][105][35];
int main(){
    int T;cin>>T;
    while(T--){
        int n,m,k;cin>>n>>m>>k;
        memset(dp,0,sizeof dp);
        for(int i=0;i<k;i++){
            string s;cin>>s;
            dx[i]=dy[i]=0;
            for(auto it:s){
                if(it=='U') dy[i]++;
                else dx[i]++;
            }
        }
        dp[0][0][0]=1;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                for(int sta=0;sta<(1<<k);sta++){
                    for(int q=0;q<k;q++){
                        int x=i-dx[q],y=j-dy[q];///(x,y) -> (i,j)
                        //越界 或没有达到(x,y)的方案
                        if(x<0 || y<0 || (!dp[x][y][sta] && !dp[x][y][sta^(1<<q)])) continue;
                        dp[i][j][sta] |= dp[x][y][sta];//行走方式之前用过
                        dp[i][j][sta] |= dp[x][y][sta^(1<<q)];//行走方式之前没用过
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<(1<<k);i++) if(dp[n][m][i]) ans=max(ans,__builtin_popcount(i));
        cout<<ans<<endl;
    }
    return 0;
}