#include<iostream> #include<string.h> #include<vector> using namespace std; int a[11][11]; int flag[11][11]; vector<int> xMax; vector<int> yMax; int pMax; void dfs(int maze[11][11],int ff[11][11],int x,int y,int p,int n,int m,vector<int> xPath,vector<int> yPath,int &maxP){ if (p < 0){ return; } if (x==0&&y==m-1){ if (maxP < p){ maxP = p; xMax = xPath; yMax = yPath; } return; } int xx[4] = {-1,1,0,0}; int yy[4] = { 0, 0, -1, 1 }; int price[4] = {3,0,1,1}; int i; for (i = 0; i < 4;i++){ int sx = x + xx[i]; int sy = y + yy[i]; if (sx >= 0 && sx < n&&sy >= 0 && sy < m&&!ff[sx][sy]&&maze[sx][sy]){ ff[sx][sy] = 1; xPath.push_back(sx); yPath.push_back(sy); dfs(maze,ff,sx,sy,p-price[i],n,m,xPath,yPath,maxP); ff[sx][sy] = 0; xPath.pop_back(); yPath.pop_back(); } } } int main(){ int n,m; while (cin>>n>>m>>pMax){ memset(a,0,sizeof(a)); memset(flag,0,sizeof(flag)); int i, j; for (i = 0; i < n;i++){ for (j = 0; j < m; j++) { int tmp; cin >> tmp; a[i][j]=tmp; } } flag[0][0] = 1; vector<int> xPath, yPath; xPath.push_back(0); yPath.push_back(0); int mm = -100; dfs(a,flag,0,0,pMax,n,m,xPath,yPath,mm); if (mm == -100){ cout << "Can not escape!" << endl; continue; } for (i = 0; i < xMax.size(); i++){ cout << "[" << xMax[i] << "," << yMax[i] << "]"; if (i<xMax.size()-1) cout << ","; } cout << endl; } system("pause"); return 0; } 难得一次全部AC的笔试