AT168 自宅からの脱出 代码与要点记录

代码如下，通过了洛谷的三个样例，但不知道为什么洛谷绑定不了atcoder的账号，不熟悉atcoder暂时找不到题......只能先这样了

洛谷题目地址：https://www.luogu.com.cn/problem/AT168

源代码如下：

#include
#include
using namespace std;
int m, n, ans;
int room[501][501],step_value[501][501];
int pcn, pcm, sn, sm, gn, gm;
const int MAX = 0x7fffffff-6;
char map[501][501];
bool moveto(int from_n, int from_m, int to_n, int to_m)
{
    if (map[to_n][to_m]=='#')return false;
    if (step_value[from_n][from_m] + 1 < step_value[to_n][to_m])
    {
        step_value[to_n][to_m] = step_value[from_n][from_m] + 1;
        return true;
    }
    else return false;
}
void bfs(int a,int b)
{
    if (moveto(a, b, a + 1, b))bfs(a + 1, b);
    if (moveto(a, b, a, b + 1))bfs(a, b + 1);
    if (moveto(a, b, a - 1, b))bfs(a - 1, b);
    if (moveto(a, b, a, b - 1))bfs(a, b - 1);
}
void set_value()
{

for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            step_value[i][j] = MAX;
        }

}
int main()
{
    cin >> n >> m;
    set_value();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == '.'|| map[i][j] == '#')continue;
            if (map[i][j] == 'S') {sn = i; sm = j;}
            else if (map[i][j] == 'C') { pcn = i; pcm = j; }
            else { gn = i; gm = j; }
        }
        
    }
    step_value[sn][sm] = 0;
    bfs(sn, sm);
    if (step_value[pcn][pcm] == MAX) { cout << '-' << '1' << endl; return 0; }
    ans = step_value[pcn][pcm];
    set_value();
    step_value[pcn][pcm] = 0;
    bfs(pcn, pcm);
    if (step_value[gn][gm] == MAX) { cout << '-' << '1' << endl; return 0; }
    ans += step_value[gn][gm];
    cout << ans << endl;
    return 0;
}

用2次bfs解决问题

值得注意的是把应该代码分块简化。。。不然看着乱实际上也很容易出问题

还有bfs前把初始点（不管是S点还是P点）的价值设为0，其他点为一个很大的值

设这个值（MAX）时注意不要让int正数溢出到负数