#include <stdio.h>
int test[1000][1000]={0}, n,dp[1000][1000]={0},p,q,r,s,w[1000][1000],x[1000][1000],y[1000][1000],z[1000][1000];
int maze[1000][1000];
int min(int a,int b)
{
return (a<b)?a:b;
}
int path(int i, int j){
test[i][j] = 1;
if(i==r && j==s)
{
test[i][j]=0;
return 0;
}
if(dp[i][j]!=0)
{
test[i][j]=0;
return dp[i][j];
}
else
{
if((j + 1) <= n && test[i][j + 1] == 0 && maze[i][j + 1] == 0)
w[i][j]=1+path(i, j + 1);
else w[i][j]=99999;
if((i + 1) <= n && test[i + 1][j] == 0 && maze[i + 1][j] == 0)
x[i][j]=1+path(i + 1, j);
else x[i][j]=99999;
if((j - 1) >= 1 && test[i][j - 1] == 0 && maze[i][j - 1] == 0)
y[i][j]=1+path(i, j - 1);
else y[i][j]=99999;
if((i - 1) >= 1 && test[i - 1][j] == 0 && maze[i - 1][j] == 0)
z[i][j]=1+path(i - 1, j);
else z[i][j]=99999;
}
test[i][j]=0;
dp[i][j]=min(min(w[i][j],x[i][j]),min(y[i][j],z[i][j]));
return dp[i][j];
}
int main(){
int i, j,ans;
for(i = 1;i <= n;i++){
for(j = 1;j <= n;j++){
scanf("%d", &maze
[i
][j
]); if(maze[i][j]==9){r=i;s=j;}
}
}
ans=path(1,1);
if(ans>900)ans=0;
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgdGVzdFsxMDAwXVsxMDAwXT17MH0sIG4sZHBbMTAwMF1bMTAwMF09ezB9LHAscSxyLHMsd1sxMDAwXVsxMDAwXSx4WzEwMDBdWzEwMDBdLHlbMTAwMF1bMTAwMF0selsxMDAwXVsxMDAwXTsKaW50IG1hemVbMTAwMF1bMTAwMF07CgppbnQgbWluKGludCBhLGludCBiKQp7CiAgICByZXR1cm4gKGE8Yik/YTpiOwp9CmludCBwYXRoKGludCBpLCBpbnQgail7CnRlc3RbaV1bal0gPSAxOwppZihpPT1yICYmIGo9PXMpCnsKICAgIHRlc3RbaV1bal09MDsKICAgIHJldHVybiAwOwp9CmlmKGRwW2ldW2pdIT0wKQogICAgewogICAgICAgIHRlc3RbaV1bal09MDsKICAgICAgICByZXR1cm4gZHBbaV1bal07CiAgICB9CmVsc2UKewppZigoaiArIDEpIDw9IG4gJiYgdGVzdFtpXVtqICsgMV0gPT0gMCAmJiBtYXplW2ldW2ogKyAxXSA9PSAwKQp3W2ldW2pdPTErcGF0aChpLCBqICsgMSk7CmVsc2Ugd1tpXVtqXT05OTk5OTsKaWYoKGkgKyAxKSA8PSBuICYmIHRlc3RbaSArIDFdW2pdID09IDAgJiYgbWF6ZVtpICsgMV1bal0gPT0gMCkKeFtpXVtqXT0xK3BhdGgoaSArIDEsIGopOwplbHNlIHhbaV1bal09OTk5OTk7CmlmKChqIC0gMSkgPj0gMSAmJiB0ZXN0W2ldW2ogLSAxXSA9PSAwICYmIG1hemVbaV1baiAtIDFdID09IDApCnlbaV1bal09MStwYXRoKGksIGogLSAxKTsKZWxzZSB5W2ldW2pdPTk5OTk5OwppZigoaSAtIDEpID49IDEgJiYgdGVzdFtpIC0gMV1bal0gPT0gMCAmJiBtYXplW2kgLSAxXVtqXSA9PSAwKQp6W2ldW2pdPTErcGF0aChpIC0gMSwgaik7CmVsc2UgeltpXVtqXT05OTk5OTsKfQp0ZXN0W2ldW2pdPTA7CmRwW2ldW2pdPW1pbihtaW4od1tpXVtqXSx4W2ldW2pdKSxtaW4oeVtpXVtqXSx6W2ldW2pdKSk7CnJldHVybiBkcFtpXVtqXTsKfQoKCmludCBtYWluKCl7CmludCBpLCBqLGFuczsKCnNjYW5mKCIlZCIsJm4pOwpmb3IoaSA9IDE7aSA8PSBuO2krKyl7CmZvcihqID0gMTtqIDw9IG47aisrKXsKc2NhbmYoIiVkIiwgJm1hemVbaV1bal0pOwppZihtYXplW2ldW2pdPT05KXtyPWk7cz1qO30KCn0KfQphbnM9cGF0aCgxLDEpOwppZihhbnM+OTAwKWFucz0wOwpwcmludGYoIiVkXG4iLGFucyk7CnJldHVybiAwOwp9Cg==