2178번임다


시간 초과라고 하는데 어떻게 바꿔야 될까요
dfs로 푸는 방식이 틀린 걸까요?

#include <iostream>


static unsigned n, m;

static unsigned vec[100][100];

static bool visit[100][100];


int dfs(unsigned y, unsigned x, unsigned cnt) noexcept {

    

    if(y == n - 1 && x == m - 1)

        return cnt;

    

    int min = 2147483647;

    

    if(x + 1 < m && !visit[y][x + 1] && vec[y][x + 1]) {

        visit[y][x + 1] = true;

        min = std::min(min, dfs(y, x + 1, cnt + 1));

        visit[y][x + 1] = false;

    }

    

    if(y + 1 < n && !visit[y + 1][x] && vec[y + 1][x]) {

        visit[y + 1][x] = true;

        min = std::min(min, dfs(y + 1, x, cnt + 1));

        visit[y + 1][x] = false;

    }

    

    if(x > 0 && !visit[y][x - 1] && vec[y][x - 1]) {

        visit[y][x - 1] = true;

        min = std::min(min, dfs(y, x - 1, cnt + 1));

        visit[y][x - 1] = false;

    }

    

    if(y > 0 && !visit[y - 1][x] && vec[y - 1][x]) {

        visit[y - 1][x] = true;

        min = std::min(min, dfs(y - 1, x, cnt + 1));

        visit[y - 1][x] = false;

    }

        

    return min;

}

/*

 4 6

 101111

 101010

 101011

 111011

 */

int main(int argc, const char * argv[]) {

    

    std::ios_base::sync_with_stdio(false);

    

    std::scanf("%d %d", &n, &m);

    

    for(int i = 0; i< n; ++i)

        for(int j = 0; j< m; ++j)

            std::scanf("%1d", &vec[i][j]);

    

    std::cout << "Starting...\n";


    visit[0][0] = true;

    std::cout << dfs(0, 0, 1);


    return 0;

}