如何查找网站,郑州企业网站建设费用,武夷山网站定制,全屋定制给设计吗题目大意#xff1a;给定一个n*m的只含0和1的矩阵#xff0c;从矩阵的最后一行中的某个1出发#xff0c;每步只能走到相邻的且是1的格子中#xff0c;求能达到的最大高度#xff08;最小行数#xff09;。 这题直接DFS即可#xff0c;复杂度为O(N*M)。 View Code 1 #in…题目大意给定一个n*m的只含0和1的矩阵从矩阵的最后一行中的某个1出发每步只能走到相邻的且是1的格子中求能达到的最大高度最小行数。 这题直接DFS即可复杂度为O(N*M)。 View Code 1 #include stdio.h2 #define MAX(a,b) ((a)(b)?(a):(b))3 #define N 1004 int dx[4]{0,0,1,-1};5 int dy[4]{1,-1,0,0};6 char g[N][N];7 int n,m,ans;8 void dfs(int i,int j)9 {
10 int d,ni,nj;
11 ansMAX(ans,n-i);
12 g[i][j]0;
13 for(d0;d4;d)
14 {
15 niidx[d],njjdy[d];
16 if(ni0 || nj0 || nin || njm || !g[ni][nj]) continue;
17 dfs(ni,nj);
18 }
19 }
20 int main()
21 {
22 int i,j;
23 while(~scanf(%d%d,n,m))
24 {
25 for(i0;in;i)
26 {
27 for(j0;jm;j) scanf(%d,g[i][j]);
28 }
29 ans0;
30 for(j0;jm;j) if(g[n-1][j]) dfs(n-1,j);
31 printf(%d\n,ans);
32 }
33 return 0;
34 } 转载于:https://www.cnblogs.com/algorithms/archive/2012/04/24/2468793.html
