题解 | #托米航空公司#

#include<bits/stdc++.h>
using namespace std;
const int mod=420047;
typedef long long  ll;
int mat[90][90];
int num=0;
int m,n,k;
void dfs(int a,int counts){
    /*
     * 这里是用来判断是否可以结束了，毕竟也不是可以一直往下走的，取决于你需要找几个位置
     * 这个题目是递归，没想到要用dfs，这是dfs吗，小白不懂。
     */
    if(counts == k){
        num++;
        return;
    }

    /*
     * 这下买的for循环i的范围是1到m*n，就是座位的个数
     * 本来我也是用了一个双重循环来做的，那样表示坐标方便，x和y就是循环变量，但是后来好像太麻烦了，又改成这样了，就是多了一个求坐标xy。
     * 
     * 这里面有一个a，是用来影响循环开始的，因为遇到了个问题。
     * 比如你找到了（1,1）这个位置，并标记了1，然后又开始dfs，总不能再从（1,1）位置开始的，要想法子从下一步开始，就是在循环开头这加a
     * 而这个a就是进入dfs时候i的值，具体看下面那个dfs。这样就达到目的了。
     */
    for(int i=a+1; i <= n * m; i++){
        /*
         * 这里的x和y需要成为局部变量，否则比如，m=2，n=3，k=2的情况，在1,1处选择了第一个座位，然后搜索遍历，在最后3,2的位置
         * 终于遍历完了之后，会回来继续选定第一个位置。可是在选第一位位置的时候，也就是从下面for循环中的dfs中出来之后有一个
         * mat[x][y]=0，本来的这个x，y应该是1和1的，可是由于是全局变量，此时的x，y是3,2，没有归零。
         */

        /*
         * 这里的x，y的坐标是座位图中的坐标从1开始，举个例子m=2，n=3，k=2的情况，
         *      0（x=1，y=1）    0（x=1，y=2）
         *      0（x=2，y=1）    0（x=2，y=2）
         *      0（x=3，y=1）    0（x=3，y=2）
         */
        int x= ceil((float)i/ m);//这里原来没有强制转换，导致x从0开始，而不是1。float(i/m)强制转换不可以，（float）i/m可以。
        int y=i%m;
        if(y==0)
            y=m;

        /*
         * 这下面的三行注释代码可以用来调试。
         */
//        cout<<"目前座位的坐标为（xy从1开始计数）："<<"x="<<x<<"，"<<"y="<<y<<"\n";
//        cout<<"当前已经选好方案数："<<num<<"\n";
//        cout<<"counts="<<counts<<"\n";
        if(mat[x - 1][y] == 0 && mat[x + 1][y] == 0 && mat[x][y - 1] == 0 && mat[x][y + 1] == 0){
            mat[x][y]=1;
                /*
                 * 这下面的也是用来调试找错误的，新手表示这样才是正确的调试改代码
                 * 硬看和在草稿纸上写真的是完全做不到呀，根本搞不会
                 */
//            cout<<"当前情况（已经选择的座位）；"<<"\n";
//            for(int i1=1;i1<=n;i1++){
//                for(int j=1;j<=m;j++){
//                    cout<<mat[i1][j]<<"\t";
//                }
//                cout<<"\n";
//            }
            counts++;//这里的counts是纪录已经选择的作为数的，如果达到了k，就不能进入dfs，或者说进入了就给你踢出来。
            dfs(i,counts);//这里一开始用的不是i，而是a+1，后来发现不对。具体的在上面for循环那里说了。
            counts--;//踢出来之后表明这次选择的座位选好了，成功找到一个方案，上面dfs中，num加一了。又要开始再继续在后面找。
            mat[x][y]=0;//既然要在后面继续找了，那么这里已经找好的，设置为没有找，然后继续循环在后面找找看看有没有符合要求的。
        }
    }

}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>m>>n>>k;
        memset(mat,0,sizeof(mat));
        num=0;
        dfs(0,0);
        cout<<num%mod<<"\n";
    }
}