让你那上面那个钥匙去插入下面那个锁里面; 问你这个钥匙能插多深. 这里的深度是指钥匙最后的底部和锁的上部的高度差; 我们首先可以让锁和钥匙左对齐; 即它们两个都靠左摆好; 设钥匙的高为n宽为m; 设锁的高为nn宽为mm 则钥匙能够往右移动的最大限度是mm-m; (这道题的设置是,如果钥匙的宽比锁长就直接输出0); 也就是说你一开始有mm-m+1个位置可以插入; 而且钥匙插入锁里面之后可以左右移动(也有mm-m+1个位置可供移动); 深度的最大值为n+nn-1,一旦大于这个值就完全插入了; 代码的模拟过程是,一个单位一个单位地把钥匙往下移动; 先看看锁能在第一层的那mm-m+1个口中的哪一些口插入; 用can[r][mm-m]表示;->bool数组; 然后从第二层开始,就可能有横移操作了; 即可能can[1][j]这个状态(就是说从第j个口不能插入); 但是can[2][j-1]这个状态(第j-1个口,能一直插到第2行)可行; 那么就能从can[2][j-1]这个状态表示的情况,再右移一位;那么就能达到 can[2][j]了;这时can[2][j]不是表示从第j个口直接往下移动2层; 而是先从第j-1个口往下移动两层,再往右移动一层; (我说的口是下面这个图所示的意思,一共mm-m+1个口)

然后如果新获得了状态can[i][j] 那么如果can[i][j-1]为false; 则让j减去1(在循环体里面要减去2,因为有个j++还没执行); 然后再看看can[i][j-1]能不能因为can[i][j]变成true了,然后can[i][j-1]本身也变成true; (即左移) 这里判断能不能到can[i][j]这个状态. 可以看一下是钥匙的一部分的地方(x,y) 其(x+i,y+j)是不是锁; 如果是钥匙的地方(x,y),对应的(x+i,y+j)都为空,就表示这个状态可以装得下这把钥匙; 同时因为can[i-1][j]或can[i][j-1]或can[i][j+1]为true; 就说明这个位置能通过移动和外界联系;则可行; 具体的看代码吧;

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100+100;

int T;
int n,m,nn,mm;
bool key[MAXN][MAXN],loc[10010][1010],can[10010][1010];
char s[1000+100];

bool in(int px,int py)
{
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            if (key[i][j] && loc[i+px][j+py])
                return false;
    return true;
}

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    cin >> T;
    while (T--)
    {
        for (int i = 1;i <= 100;i++)
            for (int j = 1;j <= 100;j++)
                key[i][j] = false;
        for (int i = 1;i <= 10000;i++)
            for (int j = 0;j <= 1000;j++)
                loc[i][j] = can[i][j] = false;
        cin >> n >> m;
        for (int i = 1;i <= n;i++)
        {
            scanf("%s",s+1);
            for (int j = 1;j <= m;j++)
                if (s[j]=='#')
                    key[i][j] = true;
        }
        cin >> nn >> mm;
        nn+=n;
        for (int i = n+1;i <= nn;i++)
        {
            scanf("%s",s+1);
            for (int j = 1;j <= mm;j++)
                if (s[j]=='#')
                    loc[i][j] = true;
        }
        for (int i = 0;i <= mm;i++)
            can[0][i] = true;
        int i;
        for (i = 1;i <= nn;i++)
        {
            bool flag = false;
            for (int j = 0;j <= mm-m;j++)
            {
                if (can[i][j]) continue;
                bool judge1 = (j-1>=0 && can[i][j-1]);
                bool judge2 = (j+1<=mm-m && can[i][j+1]);
                bool judge3 = can[i-1][j];
                if (judge1 || judge2 || judge3)
                {
                    if (in(i,j))
                    {
                       flag = true;
                       can[i][j] = true;
                       if (j-1>=0 && !can[i][j-1])
                            j-=2;
                    }
                }
            }
            if (!flag)
                break;
        }
        if (i>nn)
            puts("The key can fall through.");
        else
            printf("The key falls to depth %d.\n",i-1);
    }
    return 0;
}