[プログラマー]通学路

問題の概要

配列のサイズ(m,n)と水たまりの位置を入力します.
いつも(1,1)家(m-1,n-1)で学校にいるときは,右と下からしか学校に移動できない通学路の数を求める.(mod 1,000,000,007)

すくい取る

mは横で、nは縦です.ピットの位置も[横座標,縦座標]で与えられる.
これを裏返しに考えた.例題もあいにく[2,2]で,当てられなかった.

新学的。

memset

long long tab[100][100]={0,};0の場合のみ、同じ初期化を行うことができます.

#include<memory.h>
...
bool map[100][100];
memset(map,true,sizeof(map));

コード#コード#

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
using namespace std;
//오른쪽과 아래로만 이동 가능
bool map[100][100];
long long tab[100][100]={0,};
long long MOD= 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    memset(map,true,sizeof(map));
    for(int ctr = 0;ctr<puddles.size();ctr++){
        int i = puddles[ctr][1]-1,j = puddles[ctr][0]-1;
        map[i][j] = false;
    }
    if(map[1][0]) tab[1][0] = 1;
    if(map[0][1]) tab[0][1] =1;
    //세로를 1로 채운다.
    for(int i = 2;i<n;i++){
        if(map[i][0])
            tab[i][0] = tab[i-1][0];
    }
    //가로를 1로 채운다
    for(int j = 2;j<m;j++){
        if(map[0][j])
            tab[0][j] = tab[0][j-1];
    }
    //테이블의 나머지 네모를 채운다.
    for(int i = 1;i<n;i++){
        for(int j = 1;j<m;j++){
            if(map[i][j])
                tab[i][j] = (tab[i-1][j]+tab[i][j-1])%MOD;
        }
    }
    
    answer = tab[n-1][m-1];
    return answer;
}

軽量バージョン2

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
using namespace std;
//오른쪽과 아래로만 이동 가능
bool map[100][100];
long long tab[100][100]={0,};
long long MOD= 1000000007;
int m, n;

bool inbox(int i, int j){
    return i>=0&&i<n&&j>=0&&j<m;
}
int solution(int mm, int nn, vector<vector<int>> puddles) {
    int answer = 0;
    m = mm; n=nn;
    memset(map,true,sizeof(map));
    for(int ctr = 0;ctr<puddles.size();ctr++){
        int i = puddles[ctr][1]-1,j = puddles[ctr][0]-1;
        map[i][j] = false;
    }
    tab[0][0] = 1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(i == 0&&j ==0) continue;
            if(map[i][j]){
                tab[i][j] = ((inbox(i-1,j)?tab[i-1][j]:0)+(inbox(i,j-1)?tab[i][j-1]:0))%MOD;
            }
        }
    }
    
    answer = tab[n-1][m-1];
    return answer;
}