鸡尾酒和妹子一起逛西湖,西湖的地图用一个N*M的矩阵描述,矩阵内的元素可能有空地,墙壁,景点三种。其中景点数量Q满足Q<15,妹子希望鸡尾酒带着她们逛尽可能多的景点。初始鸡尾酒和妹子在点(1,1),鸡尾酒每次只能向上,下,左,右四个方向任选一种方向移动一格。但是由于体力有限,妹子最多进行k次移动,请问他们最多能逛多少个不同的景点。
输入第一行包含三个正整数N,M,K(1≤N,M≤300,0≤K≤1e5)接下来N行,每行M个数字,0代表空地,1代表墙壁,2代表景点.
输出一行一个整数代表答案。
3 3 5 0 2 1 0 0 1 1 1 1
1