南昌网站建设如何,怎么样制作一个公众号,用AIDE怎么建设网站,软文技巧前言#xff1a;
该题取自洛谷P1123#xff0c;题主用的dfs#xff08;深度优先搜索#xff09;
题目描述#xff1a; 数据范围#xff1a; 思路#xff1a;
思路见代码#xff0c;注释的很清晰嗷
AC代码#xff1a; #include iostream
#include alg…前言
该题取自洛谷P1123题主用的dfs深度优先搜索
题目描述 数据范围 思路
思路见代码注释的很清晰嗷
AC代码 #include iostream
#include algorithm
#include string.h //memset所在头文件
//此处使用万能头也ok题主用的VS2022不能使用万能头qvq
using namespace std;
int t;
int n, m;
int a[10][10]; //输入的矩阵的数
int vis[10][10] ; //标记该数是否被使用过
int mx 0;
void dfs(int i, int j, int sum) {//i是行j是列sum是总和//从第一个开始搜索搜索完一行进入下一行if (i n 1) {//in1时证明矩阵搜索完毕进行比较mx max(mx, sum);return;}int ii i; //ii,jj分别为下一个遍历的数的行和列int jj j 1;//当jj大于m时该行搜索完毕进入下一行if (jj m) {ii;jj 1;}//当取该数时if (vis[i - 1][j] vis[i-1][j 1] vis[i - 1][j - 1] vis[i][j - 1] vis[i][j] 0) {//判断周围是否有已选择的数因为是按顺序选择的a[i][j]之后的数不需要判断vis[i][j] 1; //将该数标记为已选择的数dfs(ii, jj, sum a[i][j]); //递归vis[i][j] 0; //回溯}dfs(ii, jj, sum); //未选择a[i][j]时sum不需要加
}
int main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin t;while (t--) {cin n m;//因为有多组数据对mx,数组avis进行初始化mx 0; memset(a, \0, sizeof(a));memset(vis, 0, sizeof(vis));for (int i 1; i n; i) {for (int j 1; j m; j) {cin a[i][j];}}dfs(1, 1, 0); //从矩阵第一个数进行搜索cout mx endl;}
}
