Niuke练习赛19托米航空公司搜索

输入描述:

输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由包含三个整数M，N和K的一行组成。

输出描述:

对于每个测试用例输出一行，表示答案对420047取模的结果。

3

2 3 2

2 4 4

2 5 1

8
2
10

备注:

T≤10

N*M<=80, K<=4

题解：

由于数据很小直接搜索即可

代码:

#include
using namespace std;
const int maxn = 100;
int n,m,k;
int ans;
int maze[maxn][maxn];
//const int dir[4][2] = {1,0,0,1,-1,0,0,-1};
void dfs(int pos,int cnt) 
{
    if(cnt == k) {
        ans++;
        return;
    }
    if(pos == n*m+1) return;
    int x = (pos - 1) / m + 1,y = (pos - 1) % m + 1;
    // printf("%d %d %d\n",pos,x,y);
    if(!maze[x-1][y] && !maze[x+1][y] && !maze[x][y+1] && !maze[x][y-1]){
        maze[x][y] = 1;
        dfs(pos+1,cnt+1);
    }
    maze[x][y] = 0;
    dfs(pos+1,cnt);
}
int main()
{
    int caset;scanf("%d",&caset);
    while(caset--) {
        scanf("%d%d%d",&n,&m,&k);
        ans = 0;        
        memset(maze,0,sizeof(maze));
        dfs(1,0);
        printf("%d\n",ans % 420047);
    }
    return 0;
}