取数字问题

蔚落 2022-07-13 13:40 182阅读 0赞

#### Problem Description ####

给定M×N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角(1,1)走到右下角(M,N)，每一步只能够向右或者向下，并且不能够走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。

#### Input ####

输入第1行是两个整数M和N,(2<=M<=10,2<=N<=10)，分别表示矩阵的行和列的数目。接下来M行，每行包括N个整数，就是矩阵中的每一行的N个元素。

#### Output ####

输出只有一行，就是一个整数，表示所选道路上数字之和所能达到的最小正整数。如果不能达到任何正整数，输出-1。

#### Example Input ####

2 2
    0 2
    1 0

#### Example Output ####

\#include<stdio.h>  
int n,m;  
int a\[16\]\[16\];  
int book\[16\]\[16\];  
int flag=0;  
void dfs (int x,int y,int mx,int my,int line\[230\]\[2\],int u)  
\{  
int i,tx,ty;  
int k=u;  
int next\[4\]\[2\]=\{ \{0,-1\},\{-1,0\},\{0,1\},\{1,0\}\};  
if(x==mx&&y==my)  
\{  
for(i=0;i<u;i++)  
\{  
if(i!=u-1)  
\{  
printf("(%d,%d)->",line\[i\]\[0\],line\[i\]\[1\]);  
\}  
else  
printf("(%d,%d)\\n",line\[i\]\[0\],line\[i\]\[1\]);  
\}  
flag=1;  
\}  
for(i=0;i<4;i++)  
\{  
tx=x+next\[i\]\[0\];  
ty=y+next\[i\]\[1\];  
if(tx<1||tx>n||ty<1||ty>m)  
continue;  
if(book\[tx\]\[ty\]==0 && a\[tx\]\[ty\]==1)  
\{  
line\[u\]\[0\]=tx;  
line\[u\]\[1\]=ty;  
k=u+1;  
book\[tx\]\[ty\]=1;  
dfs(tx,ty,mx,my,line,k);  
book\[tx\]\[ty\]=0;  
\}  
\}  
return ;  
\}  
int main()  
\{  
int i,j;  
int x,y,mx,my;  
int u=0;  
int line\[230\]\[2\]=\{0\};  
scanf("%d%d",&n,&m);  
for(i=1;i<=n;i++)  
\{  
for(j=1;j<=m;j++)  
\{  
scanf("%d",&a\[i\]\[j\]);  
\}  
\}  
scanf("%d%d%d%d",&x,&y,&mx,&my);  
book\[x\]\[y\]=1;  
line\[u\]\[0\]=x;  
line\[u\]\[1\]=y;  
u++;  
dfs(x,y,mx,my,line,u);  
if(flag==0)  
printf("-1\\n");  
return 0;  
\}