FLAPPY

AOJ FLAPPY

SOL)

DP문제

해석을 해야하는 문제 // 유추하지말고 정확히 해석하는 습관이 필요한 것 같다.

FLAP -  뛰어오르면 +4(최대 높이는 H)
STAY -  높이가 감소하는데 땅바닥에 닿으면 GAMEOVER


[-] Collapse

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cache[21][1001][21];
char board[21][1001];
int H, W;
int search(int h, int w, int stay){
    if (w > W || h < 1 || board[h][w] == '#') return w - 1;
    int &ret = cache[h][w][stay];
    if (ret != -1) return ret;
    int canFlap = 4;
    if (h + canFlap > H) canFlap = H - h;
    ret = max(search(h + canFlap, w + 1, 0), search(h - stay - 1, w + 1, stay + 1));
    return ret;
}
int main(){
    int t; scanf("%d", &t);
    while (t--){
        memset(cache, -1, sizeof(cache));
        scanf("%d%d", &H, &W);
        int sX, sY;
        for (int y = H; y >= 1; y--){
            getchar();
            for (int x = 1; x <= W; x++){
                scanf("%c", &board[y][x]);
                if (board[y][x] == '@') sY = y, sX = x;
            }
        }
        printf("%d\n", search(sY, sX, 0));
    }
}