title: 地宫寻宝-解题报告
date: 2016-03-27 16:08:28
tags: 算法
categories: 算法

问题描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

输入格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
输出格式
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

样例输入
2 2 2
1 2
2 1
样例输出
2
样例输入
2 3 2
1 2 3
2 1 5

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int total = 0;
int maze[50][50];
int squre[50][50];
int n,m,k;
int dir[2][2]={{1,0},{0,1}};
#define N 1000000007 
void dfs(int an,int am,int count,int min)
{
    //tcout<<an<<" "<<am<<endl;
    if(maze[an][am] == 0) 
    {
        //cout<<"ok"<<endl;
        return ;
    }
    if(an == 1 && am == 1)
    {
        //cout<<count<<endl; 
        if(squre[an][am] < min)
        {
            int temp = count++;
            if(temp == k)
            {
                total++;
             } 
             if(count == k)
             {
                total++;
             }
        }
        else
        {
            if(count == k)
            {
                total++;
            }
        }
    }
    else
    {
        for(int i=0;i<2;i++)
        {
            
            if(squre[an][am] < min)
            {   
                
                dfs(an-dir[i][0],am-dir[i][1],count+1,squre[an][am]);
                dfs(an-dir[i][0],am-dir[i][1],count,min);   
                    
            }
            else
            {
                dfs(an-dir[i][0],am-dir[i][1],count,min);
            }
        }
    }
 } 
int main()
{
    cin>>n>>m>>k; 
    memset(squre,0,sizeof(squre));
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>squre[i][j];
        }
    }
    memset(maze,1,sizeof(maze));

    for(int i=0;i<=n;i++)
    {
        maze[i][0] = 0;
    }
    for(int j=0;j<=m;j++)
    {
        maze[0][j] = 0;
    }
    dfs(n,m,0,100);
    cout<<total<<endl;
}