https://vjudge.net/problem/POJ-3009
做完这道题，感觉自己对dfs的理解应该又深刻了。
1.一般来说最小步数都用bfs求，但是这题因为状态记录很麻烦，所以可以用dfs。
2.在用dfs的时候，mp时一个全局变量，对于平等的走法，每一个走法结束后一定要状态复原！！！（也就是代码36-38行）否则会对其他走法产生影响。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int n, m, mp[][], si, sj, gi, gj, cnt, mini;
int dir[][] = {, , , -, , , -, };
void dfs(int x, int y, int a, int b, int k, int c)
{
if(k > ||k > mini) return ;
if(x == gi&&y == gj){
mini = min(mini, k);
return ;
}
if(a != ||b != ){//不是刚开始
if(x<||x>=n||y<||y>=m){
return;//失败
}
else if(mp[x][y] == ){
if(c <= ) return ;
c = ;
mp[x][y] = ;//该阻被消去
x -= a;
y -= b;//回到上一状态
for(int i = ; i < ; i++){
dfs(x+dir[i][], y+dir[i][], dir[i][], dir[i][], k+, c+);
}
x += a;
y += b;
mp[x][y] = ;//记住要状态复原！！
}
else{
dfs(x+a, y+b, a, b, k, c+);
}
}
else{
for(int i = ; i < ; i++){
dfs(x+dir[i][], y+dir[i][], dir[i][], dir[i][], k+, c+);
}
}
}
int main()
{
while(cin >> m >> n, n, m){
mini = INF;
cnt=;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin >> mp[i][j];
if(mp[i][j] == ) si=i,sj=j;
if(mp[i][j] == ) gi=i,gj=j;
}
}
dfs(si, sj, , , , );
if(mini == INF) cout << "-1" << endl;
else cout << mini << endl;
}
return ;
}