2176: 信息学奥赛一本通T1251-仙岛求药

解题思路:BFS比较简单， DFS需要剪枝,否则超时

注意事项:记忆节点的距离，判断当前节点的距离，以及节点距离是否小于最小值

参考代码:

#include <iostream>
#include <cstring>
#include <limits>
using namespace std;
const int N = 1e2 + 10;
int g[N][N],dis[N][N],n, m, sx, sy, ex, ey,cnt;
int mx = 0x3f3f3f3f; 
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
bool v[N][N];
void dfs(int x, int y,int lth){	
    if(x == ex && y == ey){
        if(mx > lth) mx = lth;
        return;
    }
    if(dis[x][y] > lth) dis[x][y] = lth;
    else return;
    if(lth + 1 >= mx) return;
    for(int i = 0; i < 4; i ++){
        int nx = d[i][0] + x;
        int ny = d[i][1] + y;
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && !g[nx][ny] && !v[nx][ny]){
            v[nx][ny] = true;
            dfs(nx, ny,lth + 1);
            v[nx][ny] = false; 
        }
    }
}
int main(){
    cin >> n >> m;
    while(n > 0 && m > 0){
        memset(g, 0, sizeof(g));
        memset(v, 0, sizeof(v));
        memset(dis,0x3f,sizeof(dis));
        mx = 0x3f3f3f3f;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                char c;
                cin >> c;
                if (c == '#') g[i][j] = 1;
                else if (c == '@') {
                    sx = i;
                    sy = j;
                } 
                else if (c == '*'){
                    ex = i;
                    ey = j; 
                } 
                  
            }
        v[sx][sy] = true;
        dfs(sx,sy,0);
        if (mx == 0x3f3f3f3f)
        	cout << -1 << endl;
        else cout << mx << endl;
        cin >> n >> m; 
    }
    return 0;
}