牛客708427号：枚举，map去重剪枝

win君：楼主不哭，感觉和当当网的傻叉面试官一样

seeme：#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的笔试

kop：附加题用全排列暴力做出来了。。。 void Swap(int &a, int &b) { int temp = a; a = b; b = temp; } void Permutation(vector<int> &vec, int start, int end, vector<vector<int>> &vecBig) { if(start == end) { vecBig.push_back(vec); } else { for(int i = start; i<= end; ++i) { Swap(vec[i], vec[start]); Permutation(vec, start+1, end, vecBig); Swap(vec[i], vec[start]); } } } int main() { int n; cin>>n; vector<vector<int>> vecBig; for(int i = 0; i<=n; ++i) { vector<int> vecTemp; string str; getline(cin, str); for(int j = 0; j< str.size(); ++j) { if(str[j] == ',') str[j] = ' '; } istringstream ss(str); int num; while(ss>>num) { vecTemp.push_back(num); } if(i!= 0) { vecBig.push_back(vecTemp); } } vector<int> vect; for(int i = 0; i< n; ++i) { vect.push_back(i); } vector<vector<int>> vec; Permutation(vect, 0, n-1, vec); int min = 99999; for(int i = 0; i< vec.size(); ++i) { int curMid = 0; vector<int> vect = vec[i]; int pre = vect[0]; for(int j = 1; j<vect.size(); ++j) { int cur = vect[j]; curMid +=vecBig[pre][cur]; pre = cur; } if(curMid<min) min = curMid; } cout<<min<<endl; }