1154:LETTERS

keyword

探索　DFS　C++

概要

w*h(w,h<20)のボードが与えられる。各セルにはアルファベットが入っている。左上から一度踏んだアルファベットはもう踏まないという条件で歩いて回るとき、最大で何文字のアルファベットを踏めるかを求める問題。DFSで普通に探索すると最大ケースでTLEになるかもしれないと思ったけれど手元でサイズ最大のランダムケースに対して一瞬で計算終了したので大丈夫だと信じてsubmit。無事AC。

int mark, best, w, h;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
vector<string> board;

void dfs(int y, int x){
    if(x < 0 || x >= w || y < 0 || y >= h || (mark & (1<<(board[y][x]-'A')))) return ;
    int i;
    mark |= 1<<(board[y][x]-'A');
    best = max(best, __builtin_popcount(mark));
    REP(i,4){
        dfs(y+dy[i], x+dx[i]);
    }
    mark &= ~(1<<(board[y][x]-'A'));
    return ;
}

int main(){
    mark = 0;
    best = 0;
    int i;
    string line;
    scanf("%d%d\n",&h,&w);
    REP(i,h){
        cin >> line;
        board.PB(line);
    }
    dfs(0,0);
    printf("%d\n",best);
}