[BOJ/백준][Gold2] 17090 : 미로 탈출하기 (C++)

https://www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

 

 

[난이도] Gold2
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 미로에서 탈출 가능하면 1, 아니면 0

 

 

#include <cstdio>
#include <cstring>
using namespace std;
int N,M,ans,visit[501][501],dp[501][501],board[501][501],dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
int sol(int y,int x){
    visit[y][x]=1;
    int& ret =dp[y][x];
    if(ret!=-1) {
        visit[y][x]=0;
        return ret;
    }
    int d = board[y][x];
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=N||nx>=M) ret=1;
    else {
        if(visit[ny][nx]) ret=0;
        else ret = sol(ny,nx);
    }
    visit[y][x]=0;
    return ret; 
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            char d;
            scanf(" %c",&d);
            if(d=='R') board[i][j]=1;
            else if(d=='D') board[i][j]=2;
            else if(d=='L') board[i][j]=3;
        }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            ans+=sol(i,j);
        }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/17090.cpp