wannafly 挑战赛10 小H和密码

题意：中文题就不解释了

题解： dp[i][j]表示前i 个轮盘 和一个字符串前j 个字符的匹配情况 ，具体的状态转移解释见代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

using namespace std;

int n,m,q;

int vis[][];

int dp[][];

int main()

{

    cin>>n>>m>>q;

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++)// lunpan

    {

        string s;

        cin>>s;

        for(int j=;j<m;j++)// meiyi wei

        {

            if(s[j]=='#') vis[i][]=;// '#'

            else vis[i][s[j]-'a']=;

        }

    }

    while(q--)

    {

        char s[];

        scanf("%s",s+);

        memset(dp,,sizeof(dp));

        int len=strlen(s+);

        if(len > n)

        {

            cout<<"NO"<<endl;

            continue;

        }

        dp[][]=;// 初始情况，这个地方好好琢磨一下 写的时候还是出了很多细节问题

        for(int i=;i <= n;i++) // lunpan

        {

            for(int j=;j<=len;j++)

            {

                if(dp[i][j] == ) continue; // 如果当前位置无法匹配 那就不需要进行之后的匹配了

                if(vis[i+][s[j+]-'a'] == ) dp[i+][j+] = ; // i+1 和j+1位置 的字符能够匹配且dp[i][j]==1  那么能够匹配

                if(vis[i+][] == ) dp[i+][j] = ; // 如果i+1有‘#’字符且dp[i][j]==1，那么dp[i+1][j]的值也就是1了

            }

        }

        if(dp[n][len] == ) cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return ;

}