Pick numbers

Description
Given a matrix of size M*N, the elements of which are integer numbers from -10 to 10. You task is to go from the top-left corner (1, 1) to the bottom-right corner (M, N). You can only move right or down, and you can not go out of the matrix. The number in the grid you passed must be picked. The sum of numbers you picked must be positive and as minimal as possible.
Input
 
The input contains several test cases.
      The first line of each test case are two integer numbers M, N (2<=M<=10, 2<=N<=10), indicating the number of rows and columns of the matrix. The following M lines, each contains N integer numbers.
 
Output
For each test case, output the sum of numbers you picked on a single line. If you can't get a positive sum, output -1.
Sample Input
Copy sample input to clipboard
 
2 2
0 2
1 0
3 3
0 0 0
0 0 0
0 0 0
 
Sample Output
 
1
-1
제목: M * N 의 칸 을 주 십시오. 지금 은 왼쪽 위 에서 오른쪽 아래 까지 가 야 합 니 다. 그리고 아래 나 오른쪽으로 만 갈 수 있 습 니 다. 그리고 지나 간 칸 의 수 를 더 해 야 합 니 다. 지금 은 요구 와 위 치 를 정 하고 작 을 수록 좋 습 니 다. 화 해 를 구 합 니 다.
bfs 를 이용 하여 최소 값 을 구하 다.

#include<cstdio>
#include<queue>

using namespace std;

#define MAX 100000
int ans,row,col;
int map[11][11];
int dir[2][2]={1,0,
               0,1};

struct node{
    int row;
    int col;
    int sum;
};
void bfs()
{
    queue<node> que;
    node first;
    first.row = 1;
    first.col = 1;
    first.sum = map[1][1];
    que.push(first);
    node p,temp;
    while(!que.empty())
    {
        p = que.front();
        que.pop();
        if(p.row == row&&p.col == col&&p.sum>0)
        {
            ans = min(p.sum,ans);
        }

        for(int i = 0;i < 2;i++)
        {
            temp = p;
            temp.row += dir[i][0];
            temp.col += dir[i][1];
            if(temp.row >=1 && temp.col>=1 && temp.row<=row && temp.col<=col)
            {
                temp.sum += map[temp.row][temp.col];
                que.push(temp);
            }
        }
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    int i,j;
    while(scanf("%d%d",&row,&col)==2)
    {
        ans = MAX;
        for(i=1;i<=row;i++)
            for(j=1;j<=col;j++)
            scanf("%d",&map[i][j]);
        bfs();
        if(ans == MAX)
            printf("-1
");
        else
            printf("%d
",ans);
    }
}

데이터 양 이 비교적 작 기 때문에 우 리 는 dfs 를 이용 할 수 있다.

#include<cstdio>
#include<queue>

using namespace std;

#define MAX 100000
int ans,row,col;
int map[11][11];
int dir[2][2]={1,0,
               0,1};


void dfs(int r,int c,int sum)
{
    if(r==row && c == col)
    {
        if(sum > 0 && sum < ans)
        {
             ans = sum;
        }
        return;
    }
    if(r+1>=1 && r+1<=row && c>=1&& c<=col)
    {
         dfs(r+1,c,sum+map[r+1][c]);
    }


    if(r>=1 && r<=row && c+1>=1&& c+1<=col)
    {
        dfs(r,c+1,sum+map[r][c+1]);
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    int i,j;
    while(scanf("%d%d",&row,&col)==2)
    {
        ans = MAX;
        for(i=1;i<=row;i++)
            for(j=1;j<=col;j++)
            scanf("%d",&map[i][j]);
        //bfs();
        dfs(1,1,map[1][1]);
        if(ans == MAX)
            printf("-1
");
        else
            printf("%d
",ans);
    }
}