2025.7.4
/*
//28218
#include<stdio.h>
int n, m, k, a;
char str[305][305]={};
int f(int x, int y, int cnt)
{
int i;
if(x==n-1&&y==m-1){
a=cnt;
return 0;
}
if(cnt>=a){
return 0;
}
if(str[x+1][y]=='.'){
f(x+1, y, cnt+1);
}
if(str[x][y+1]=='.'){
f(x, y+1, cnt+1);
}
for(i=0; i<k; i++){
if(str[x+i+1][y+i+1]=='.'){
f(x+i+1, y+i+1, cnt+1);
}
}
return a;
}
int main()
{
int i, q, x, y, b;
scanf("%d%d%d", &n, &m, &k);
for(i=0; i<n; i++){
scanf("%s", str[i]);
}
scanf("%d", &q);
for(i=0; i<q; i++){
a=10000;
scanf("%d%d", &y, &x);
b=f(x-1, y-1, 0);
if(b%2==1){
printf("First\n");
}
else{
printf("Second\n");
}
}
return 0;
}*/
//2178
#include<stdio.h>
int map[105][105]={};
int n, m;
int a[4]={1, -1, 0, 0};
int b[4]={0, 0, 1, -1};
int result=10000;
int bfs(int x, int y, int cnt)
{
int i;
for(i=0; i<4; i++){
if(map[x+a[i]][y+b[i]]==1){
bfs(x+a[i], y+b[i], cnt+1);
}
}
if(x==n-1&&y==m-1){
if(cnt<result){
result=cnt;
}
return result;
}
}
int main()
{
int i, j;
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++){
for(j=1; j<=m; j++){
scanf("%1d", &map[i][j]);
}
}
/*for(i=0; i<=n+1; i++){
for(j=0; j<=m+1; j++){
if(i==0||i==n+1||j==0||j==m+1){
map[i][j]=-1;
}
}
}*/
int c=bfs(0, 0, 0);
printf("%d", c);
return 0;
}