BOJ-2178

#include <iostream>

using namespace std;

int N, M;
char map[101][101]; 
bool visit[101][101]; 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int ans = 10001;

void dfs(int x, int y, int depth) {
	if (x<0 || y<0 || x>=N || y>=M) return; 
	if (x==N-1 && y==M-1) {
		if (depth < ans) ans = depth;
		return;
	}

	for (int i=0; i<4; i++){
		int xa = x+dx[i];
		int ya = y+dy[i];
		if (!visit[xa][ya] && map[xa][ya] == '1') {
			visit[xa][ya] = true;
			dfs(xa, ya, depth+1);
			visit[xa][ya] = false;
		}
	}
	
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
	
    scanf("%d %d", &N, &M); 
	for (int i=0; i<N; i++) scanf("%s", map[i]);
	
	dfs(0, 0, 1);
	printf("%d\n", ans);
}