对我来说比较新鲜的搜索题
没见过这种类型的搜索题
我看着要一个一个的枚举但是我这有点不知道怎么下手
这里实际上用了递归一层一层的 y++ 到 x++ 然后超过边界进行下一次不重复的枚举
这里还得感慨一下回溯算法, 计算机被治的枚举很听话了, 不重复的各种条件的枚举
这里有选择这个点或者不选择这个点的 dfs 的区分
有点 dp 的感觉, 但是目前想不到什么好的 dp 思路
代码
- #include <bits/stdc++.h>
- using namespace std;
- int sum,mp[666][666],n,m,bk[666][666];
- void dfs(int x,int y,int re)
- {
- if(x>n)
- {
- sum=max(sum,re);
- return;
- }
- int xx=x,yy=y+1;
- if(yy>m)
- yy=1,xx++;
- if(!bk[x][y]&&!bk[x-1][y]&&!bk[x-1][y-1]&&!bk[x-1][y+1]&&!bk[x][y-1]&&!bk[x][y+1]&&!bk[x+1][y]&&!bk[x+1][y-1]&&!bk[x+1][y+1])
- {
- bk[x][y]=1;
- dfs(xx,yy,re+mp[x][y]);
- bk[x][y]=0;
- }
- dfs(xx,yy,re);
- }
- int main()
- {
- iOS::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin>>t;
- while(t--)
- {
- sum=0;
- memset(bk,0,sizeof(bk));
- cin>>n>>m;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- cin>>mp[i][j];
- dfs(1,0,0);
- cout<<sum<<"\n";
- }
- }
来源: http://www.bubuko.com/infodetail-2946017.html