这道题规定了方向,向右或者向下,dfs深度优先搜索,可以想象成选定一个方向,然后一头扎进去,不撞南墙不回头,最终就是结束一个个递归然后从合适的位置再扎进去
#include<iostream> #include<set> using namespace std; set<int>q; //使用set容器可以自动去重和排序 int map[1000][1000]; //存储每个位置的值 int n; //地图的大小 void dfs(int x,int y,int sum){ //表示行,列,值的大小 if(x==n&&y==n){ q.insert(sum); return; } if(x<=n){ dfs(x+1, y, sum+map[x+1][y]); //向下 } if(y<=n){ dfs(x, y+1, sum+map[x][y+1]); //向右 } return; //结束递归调用 }; int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>map[i][j]; } } dfs(1, 1, map[1][1]); cout<<q.size()<<endl; return 0; }dfs能做的,bfs也能做,且可以不用使用递归,用bfs解题能更容易找到图的最短路径,不过与这个题没有太大的关联,具体过程就是每遍历到一个点,先判断是不是符合要求,若符合就把它压入队列中,等它被取出,再将它四周的点取出来放进队列,循环这个操作。
#include<iostream> #include<set> #include <queue> using namespace std; set<int>q;//使用set容器可以自动去重和排序 struct node{ int x;int y;int num;//保存位置(行,列)和值 }; queue<node>p; int map[1000][1000]; int n; int dir[2][2]={{1,0},{0,1}};//控制方向,下,右 void bfs(int x,int y ){ //初始位置传入 node k({1,1,map[1][1]}); p.push(k); while(!p.empty()){ node u=p.front(); p.pop(); if(u.x==n&&u.y==n){ q.insert(u.num); } for(int i=0;i<2;i++){ int xx=u.x+dir[i][0]; int yy=u.y+dir[i][1]; if(xx>0&&xx<=n&&yy<=n&&yy>0){ int sum=u.num+map[xx][yy]; node t({xx,yy,sum}); p.push(t); } } } }; int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>map[i][j]; } } bfs(1,1); cout<<q.size()<<endl; return 0; }