这道题目主要是dfs+记忆化搜索。
dfs就不说了,这道题的dfs只有mp需做一下处理其余没有区别。
重点是记忆化搜索:坑
1.需要两个vector来记录路径,因为只用一个的话会被盖,最后只剩下0和0还有0。
2.巨坑:起点可能是墙!!!!!!!!!!!!!!!!!!!
我也只是默默的掏出了板砖而已。
程序:
#include<bits/stdc++.h> using namespace std; int n,m,p,q,mp[20][20]={0},ans=0,vis[20][20]={0},cnt,d[10][10]={{1,0},{0,1}}; vector <int> step; vector <int> ans_step; void dfs(int x,int y,int k) { if(x==n&&y==m) { cnt=1; if(k>ans) { ans=k; ans_step=step; } return; } else { for(int i=0;i<2;i++) { int nx=x+d[i][0],ny=y+d[i][1]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0&&mp[nx][ny]!=-1) { vis[nx][ny]=1; step.push_back(nx); step.push_back(ny); dfs(nx,ny,k+mp[nx][ny]); step.pop_back(); step.pop_back(); vis[nx][ny]=0; } } } } int main() { scanf("%d%d%d%d",&n,&m,&p,&q); for(int i=1;i<=p;i++) { int x2,y2; scanf("%d%d",&x2,&y2); mp[x2][y2]=-1; } for(int i=1;i<=q;i++) { int x2,y2,money; scanf("%d%d%d",&x2,&y2,&money); mp[x2][y2]=money; } if(mp[1][1]!=-1) { step.push_back(1); step.push_back(1); dfs(1,1,mp[1][1]); } else { printf("-1\n"); return 0; } if(cnt==1) { printf("%d\n",ans); for(int i=0;i<ans_step.size();i+=2) { if(i!=ans_step.size()-2) printf("(%d,%d)->",ans_step[i],ans_step[i+1]); else printf("(%d,%d)",ans_step[i],ans_step[i+1]); } } else { printf("-1\n"); } return 0; }