2021.11.07 / bfs(EDG夺冠)
题目名：仙岛求药
https://www.acwing.com/problem/content/1101/
写道简单题缓缓

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int tt, n, m, dist[310][310];
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

bool st[310][310];
queue<pii> q;
pii start, ed;

bool value(int x, int y){//判断是否越界
    return x >= 0 && y >= 0 && x < n && y < m; 
}

//得到距离函数
int solve(){
    //因为有多组数据，所以记得初始化数组哦
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    while(q.size()) q.pop();

    //输入
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == '#') st[i][j] = 1;
            else if(s[j] == '@') start.first = i, start.second = j;
            else if(s[j] == '*') ed.first = i, ed.second = j;
        }
    }
    //处理起点
    q.push(start); dist[start.first][start.second] = 0;

    //BFS
    while(q.size()){
        int nowx = q.front().first, nowy = q.front().second;//取出当前坐标
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = nowx + dx[i], ny = nowy + dy[i];//得到下一个坐标
            if(value(nx, ny) && !st[nx][ny]){//如果坐标没越界 && 没被访问过
                //如果是重点直接返回答案
                if(make_pair(nx, ny) == ed) return dist[nowx][nowy] + 1;
                //更新下一个坐标的距离，并且放入队列中
                dist[nx][ny] = dist[nowx][nowy] + 1;
                q.push({nx,ny});
                st[nx][ny] = 1;
            }
        }
    }
    return -1;
}

int main(){
    while(cin >> n >> m && n && m){
        cout << solve() << endl;;
    }

    return 0;
}