[SWEA] 1824 혁진이의 프로그램 검증

이 문제는 써있는게 요란해서 그렇지 사실 dp로 풀면 바로 풀 수 있다!

우리가 생각해야할 조건은 4가지다 x,y,숫자,방향!

 

dp테이블을 d[x][y][num][dir]로 잡아보자!!

 

다 잡았으면 이제 dp테이블의 값을 생각해보자

d[x][y][num][dir]은 바로 x,y위치에서 num의 숫자를 가지고 dir 방향으로 갈 때 

처음 방문하는곳이라면 -1 , 이미 방문했으면 0, 멈출 수 있다면 1이다!

 

이제 각 문자에 맞게 조건을 return 해주면 된다!

0,0 에서 시작해서 1이 될 수 있는지 봐야하므로 비트연산 or 을통해 계속 return 해주자!

 

나는 소스 중복되는 부분이 많게 풀었다..!

4방향 가는거 함수 하나로 만들어서 해도되는데..! 

다들 짧게 푸시길!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
char map[22][22];
int d[22][22][18][6];
int r,c;
 
int solve(int x,int y,int num,int dir){
    if(map[x][y]=='@') return 1;
    int &ret = d[x][y][num][dir];
    if(ret != -1) return ret;
    ret = 0;
 
    char op = map[x][y];
    if(op=='<') ret|=solve(x,((y-1)+c)%c,num,0);
    else if(op=='>') ret|=solve(x,(y+1)%c,num,1);
    else if(op=='^') ret|=solve(((x-1)+r)%r,y,num,2);
    else if(op=='v') ret|=solve((x+1)%r,y,num,3);
    else if(op=='_') {
        if(num==0) ret|=solve(x,(y+1)%c,num,1);
        else ret|=solve(x,((y-1)+c)%c,num,0);
    }
    else if(op=='|') {
        if(num==0) ret|=solve((x+1)%r,y,num,3);
        else ret|=solve(((x-1)+r)%r,y,num,2);
    }
    else if(op=='?'){
        ret|=solve(x,((y-1)+c)%c,num,0);
        ret|=solve(x,(y+1)%c,num,1);
        ret|=solve(((x-1)+r)%r,y,num,2);
        ret|=solve((x+1)%r,y,num,3);
    }
    else if(op=='.') {
        if(dir==0) ret|=solve(x,((y-1)+c)%c,num,dir);
        else if(dir==1) ret|=solve(x,(y+1)%c,num,dir);
        else if(dir==2) ret|=solve(((x-1)+r)%r,y,num,dir);
        else if(dir==3) ret|=solve((x+1)%r,y,num,dir);
    }
    else if('0'<=op && op<='9'){   
        if(dir==0) ret|=solve(x,((y-1)+c)%c,op-'0',dir);
        else if(dir==1) ret|=solve(x,(y+1)%c,op-'0',dir);
        else if(dir==2) ret|=solve(((x-1)+r)%r,y,op-'0',dir);
        else if(dir==3) ret|=solve((x+1)%r,y,op-'0',dir);
    }
    else if(op=='+') {
        if(dir==0) ret|=solve(x,((y-1)+c)%c,(num+1)%16,dir);
        else if(dir==1) ret|=solve(x,(y+1)%c,(num+1)%16,dir);
        else if(dir==2) ret|=solve(((x-1)+r)%r,y,(num+1)%16,dir);
        else if(dir==3) ret|=solve((x+1)%r,y,(num+1)%16,dir);
    }
    else {
        if(dir==0) ret|=solve(x,((y-1)+c)%c,(num+15)%16,dir);
        else if(dir==1) ret|=solve(x,(y+1)%c,(num+15)%16,dir);
        else if(dir==2) ret|=solve(((x-1)+r)%r,y,(num+15)%16,dir);
        else if(dir==3) ret|=solve((x+1)%r,y,(num+15)%16,dir);
    }
    return ret;
}
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int p=1;
    while(tc--){
        memset(map,0,sizeof(map));
        memset(d,-1,sizeof(d));
        
        scanf(" %d %d",&r,&c);
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                scanf(" %1c",&map[i][j]);
            }
        }
        int ans = solve(0,0,0,1);
        string print = ans ? "YES" : "NO";
        cout<<"#"<<p++<<" "<<print<<"\n";
    }
}