P1027 （C语言代码） dfs

解题思路:





注意事项:





参考代码:

#include<stdio.h>

int r,c,max;

int a[41][41],b[41][41];

void dfs(int x,int y,int sum)

{

int i,j,tx,ty,m=-1;

if(x==r&&y==c)

{

if(max<sum)

max=sum;

return;

}

if(x+1<=r&&b[x+1][y]==0&&m<a[x+1][y])

{

tx=x+1;ty=y;m=a[tx][ty];

}

if(x-1>=1&&m<a[x-1][y]&&b[x-1][y]==0)

{

tx=x-1;ty=y;m=a[tx][ty];

}

if(y+1<=c&&m<a[x][y+1]&&b[x][y+1]==0)

{

tx=x;ty=y+1;m=a[tx][ty];

}

if(y-1>=1&&m<a[x][y-1]&&b[x][y-1]==0)

{

tx=x;ty=y-1;m=a[tx][ty];

}

b[tx][ty]=1;

dfs(tx,ty,sum+a[tx][ty]);

b[tx][ty]=0;

}

int main()

{

int i,j;

scanf("%d%d",&r,&c);

for(i=1;i<=r;i++)

for(j=1;j<=c;j++)

scanf("%d",&a[i][j]);

max=a[1][1];

b[1][1]=1;

dfs(1,1,a[1][1]);

printf("%d\n",max);

return 0;

}