#include <iostream> #include <vector> #include <climits> using namespace std; vector<vector<int> > map; int maxf = INT_MIN; vector<pair<int,int>> shortesresult; /* To find the path with least cost; Move left or right costs 1 Move Up costs 3 Move down costs 0 input: 4 4 10 // n m p p is total allowed cost 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 */ bool dfs(int x,int y,int n,int m,int p,vector<pair<int,int>> &result){ if(p <= 0){ return false; //  } if(x == 0 and y == m){ result.push_back({x,y}); for(auto &p : result){ //cout << '[' << p.first << "," << p.second << ']'; } //cout << p << endl; if(p > maxf){ shortesresult = result; maxf = p; } result.pop_back(); // bug!!!!!! return true; } if(x < 0 || y < 0 || x > n || y > m ){ return false; } if(map[x][y] <= 0){ return false; } //cout << x << " " << y << " " << p << endl; result.push_back({x,y}); map[x][y] = -1; bool r1 = dfs(x + 1,y,n,m,p,result); bool r2 = dfs(x,y + 1,n,m,p - 1,result); bool r3 = dfs(x,y - 1,n,m,p - 1,result); bool r4 = dfs(x - 1,y,n,m,p -  3,result); result.pop_back(); map[x][y] = 1; return false; } int main(){ int n,m,p,tmp; cin >> n >> m >>p; map = vector<vector<int> >(n,vector<int>(m,0)); for(int i = 0; i < n; i ++){ for(int j = 0;j < m;j ++){ cin >> tmp; map[i][j] = tmp; } } vector<pair<int,int>> result; bool isFirst = true; dfs(0,0,n-1,m-1,p,result); if(shortesresult.size() != 0){ for(auto &p : shortesresult){ if(!isFirst){ cout << ','; } cout << '[' << p.first << "," << p.second << ']'; isFirst = false; } }else{ cout << "Can not escape!" << endl; } cout << endl; }