西湖奇遇记Ⅱ
题号:NC25595
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

鸡尾酒和妹子一起逛西湖,西湖的地图用一个N*M的矩阵描述,矩阵内的元素可能有空地,墙壁,景点三种。其中景点数量Q满足Q<15,妹子希望鸡尾酒带着她们逛尽可能多的景点。初始鸡尾酒和妹子在点(1,1),鸡尾酒每次只能向上,下,左,右四个方向任选一种方向移动一格。但是由于体力有限,妹子最多进行k次移动,请问他们最多能逛多少个不同的景点。

输入描述:

输入第一行包含三个正整数N,M,K(1≤N,M≤300,0≤K≤1e5)

接下来N行,每行M个数字,0代表空地,1代表墙壁,2代表景点.

输出描述:

输出一行一个整数代表答案。
示例1

输入

复制
3 3 5
0 2 1
0 0 1
1 1 1

输出

复制
1