白駿17070号:移動パイプ1

質問する

題ショートカットキー>白駿17070号:移動パイプ1

に答える

パイプの位置をチェックし,dfs探索を行えば問題を簡単に解決できる.しかし、私は最初にパイプの移動が成功したかどうかをチェックするのは間違っていて、home[y][x]は1かもしれませんが、対角線であれば、周囲は1かもしれませんので、まずチェックが必要です!!!(私だけバカみたいに間違ってたけど、ははは)

dfsを使用したプール

#include<iostream>
#define MAX_N 17
using namespace std;

int N, ans = 0;
int home[MAX_N][MAX_N]; // 집의 상태

void dfs(int y, int x, int state){
    if(N<x || N<y || home[y][x] || (state==2 && (home[y-1][x] || home[y][x-1]))) // 범위를 벗어난 경우, 벽이 있는 경우
        return;
    if(x==N && y==N){ // 파이프 이동 성공
        ans++;
        return;
    }
    if(state==0){ //가로 
        dfs(y, x+1, 0);
        dfs(y+1, x+1, 2);
    }
    else if(state==1){ //세로
        dfs(y+1, x, 1);
        dfs(y+1, x+1, 2);
    }
    else if(state==2){ //대각선
        dfs(y, x+1, 0);
        dfs(y+1, x, 1);
        dfs(y+1, x+1, 2);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) cin >> home[i][j];
    }
    dfs(1, 2, 0); // (1, 2) , 가로
    cout << ans;
}

また,この問題は,(N,N)に到達する方法に横,縦,対角線の3つの方法があり,dpを用いて解決することもできる.3차원 array(행, 열, (가로,세로,대각선))=>int dp[17][17][3]を宣言し、dp[1][2][0]=1でdpを行った.dpを使うと多くの時間を節約できます!

dpを用いて解く

#include<iostream>
#include<cstring>
#define MAX_N 17
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int home[MAX_N][MAX_N], dp[MAX_N][MAX_N][3];
    memset(dp, 0, sizeof(dp)); // 초기화 
    dp[1][2][0]=1; // 초기화 
    
    int N; cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) cin >> home[i][j];
    }
    for(int i=1; i<=N; i++){ // dp (반복문을 돌면서 값을 하나씩 update해나감)
        for(int j=3; j<=N; j++){
            if(home[i][j]) continue;
            dp[i][j][0] = dp[i][j-1][0]+dp[i][j-1][2]; // 가로
            dp[i][j][1] = dp[i-1][j][1]+dp[i-1][j][2]; // 세로
            if(!home[i-1][j] && !home[i][j-1]) // 대각선의 경우 추가 검사 필요
                dp[i][j][2] = dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2]; // 대각선
            else dp[i][j][2]=0;
        }
    }
    cout << dp[N][N][0] + dp[N][N][1] + dp[N][N][2]; // 가로, 세로, 대각선 도착 가짓수을 모두 더하면 총 도착 가짓수
}