zhcnyuyang 于 2016.09.25 15:00 提问

#include
#include
using namespace std;
int w[100],h[100];
int arr[100][21][21];
int output[100];
int main(){

``````extern int dfs(int,int,int,int);
for(int i=1;i<=99;i++){
output[i]=-1;
}
int i=0;
for(;;){
int w0,h0;
i++;
scanf("%d %d",&w[i],&h[i]);
if(w[i]==0&&h[i]==0){
i=i-1;
break;
}
for(int j=1;j<=h[i];j++){
for(int k=1;k<=w[i];k++){
scanf("%d",&arr[i][j][k]);
if(arr[i][j][k]==2){
w0=k;
h0=j;
}
}
}
dfs(h0,w0,1,i);
}
for(int l=1;l<=i;l++){
printf("%d\n",output[l]);
}
return 0;
``````

}

void dfs(int x,int y,int step,int t){

``````if(step>10){
return;
}
if(arr[t][x][y]==3){
if(output[t]==-1){
output[t]=step;
}else if(output[t]!=0){
if(step<output[t]){
output[t]=step;
}
}
}//paichu
else{
int a0[21][21];
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
a0[i][j]=arr[t][i][j];
}
}
//left
if(y>1&&arr[t][x][y-1]!=1){
int judge=0;
int y1;
for(int i=y;i>=1;i--){
if(arr[t][x][i]==1){
judge=1;
y1=i+1;
arr[t][x][i]=0;
break;
}
if(arr[t][x][i]==3){
judge=3;
y1=i;
break;
}
}
if(judge==1){
dfs(x,y1,step+1,t);
}else if(judge==3){
dfs(x,y1,step,t);
}
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
arr[t][i][j]=a0[i][j];
}
}
}
//right
if(y<w[t]&&arr[t][x][y+1]!=1){
int judge=0;
int y1;
for(int i=y;i<=w[t];i++){
if(arr[t][x][i]==1){
judge=1;
y1=i-1;
arr[t][x][i]=0;

break;
}
if(arr[t][x][i]==3){
judge=3;
y1=i;

break;
}
}
if(judge==1){
dfs(x,y1,step+1,t);
}else if(judge==3){
dfs(x,y1,step,t);
}
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
arr[t][i][j]=a0[i][j];
}
}
}
//up
if(x>1&&arr[t][x-1][y]!=1){
int judge=0;
int x1;

for(int i=x;i>=1;i--){
if(arr[t][i][y]==1){
judge=1;
x1=i+1;
arr[t][i][y]=0;

break;
}
if(arr[t][i][y]==3){
judge=3;
x1=i;

break;
}
}

if(judge==1){
dfs(x1,y,step+1,t);
}else if(judge==3){
dfs(x1,y,step,t);
}
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
arr[t][i][j]=a0[i][j];
}
}
}
//down
if(x<h[t]&&arr[t][x+1][y]!=1){
int judge=0;
int x1;

for(int i=x;i<=h[t];i++){
if(arr[t][i][y]==1){
judge=1;
x1=i-1;
arr[t][i][y]=0;

break;
}
if(arr[t][i][y]==3){
judge=3;
x1=i;

break;
}
}

if(judge==1){
dfs(x1,y,step+1,t);
}else if(judge==3){
dfs(x1,y,step,t);
}
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
arr[t][i][j]=a0[i][j];
}
}
}
}
``````

}

1个回答

caozhy      2016.09.25 23:52