I - Fire! UVA - 11624

旧城等待， 2022-06-15 02:17 148阅读 0赞

Think:  
1两点BFS，第一遍预处理火到每个结点的时间，第二遍遍历判断是否可以走出迷宫，以及得到走出迷宫的最短时间  
2注意时间和数组越界

[vjudge题目链接][vjudge]

以下为Time limit Exceeded代码——未优化+数组越界（尚未判断）

#include <cstdio>
    #include <cstring>
    #define Inf 0x3f3f3f3f
    
    using namespace std;
    
    struct node
    {
        int x, y;
        int step;
    } link_J[1040000], link_F[1040000], p, q;
    
    int n, m, u[104][104];
    bool v[104][104];
    char st[104][104];
    int jk[4][2] = {
       {
       0, 1}, {
       1, 0}, {
       0, -1}, {-1, 0}};
    
    void BFS();
    bool Judge(int dx, int dy);
    
    int main()
    {
        int T, i;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%d %d", &n, &m);
            for(i = 0; i < n; i++)
                scanf("%s", st[i]);
            BFS();
        }
        return 0;
    }
    bool Judge(int dx, int dy)
    {
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
            return false;
        else
            return true;
    }
    void BFS()
    {
        int jo, jt, fo, ft, i, j, a, b, c, d;
        int flag = -1;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                u[i][j] = Inf;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(st[i][j] == 'F')
                {
                    c = i, d = j;
                    flag += 1;
                }
                else if(st[i][j] == 'J')
                {
                    a = i, b = j;
                    flag += 1;
                }
                if(flag == 1)
                    break;
            }
            if(flag == 1)
                break;
        }
    
        jo = jt = fo = ft = 0;
        memset(v, true, sizeof(v));
        p.x = c;
        p.y = d;
        p.step = 0;
        link_F[ft++] = p;
        v[p.x][p.y] = false;
        u[p.x][p.y] = 0;
        while(fo < ft)
        {
            p = link_F[fo];
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    u[q.x][q.y] = q.step;
                    link_F[ft++] = q;
                }
            }
            fo++;
        }
    
        flag = 0;
        memset(v, true, sizeof(v));
        p.x = a;
        p.y = b;
        p.step = 0;
        if(p.step < u[p.x][p.y])
        {
            link_J[jt++] = p;
            v[p.x][p.y] = false;
        }
        while(jo < jt)
        {
            p = link_J[jo];
            if(p.x == 0 || p.x == n-1 || p.y == 0 || p.y == m-1)
            {
                flag = 1;
                printf("%d\n", p.step+1);
                break;
            }
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && q.step < u[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    link_J[jt++] = q;
                }
            }
            jo++;
        }
        if(!flag)
            printf("IMPOSSIBLE\n");
    }

以下为Runtime Error代码——数组越界

#include <cstdio>
    #include <cstring>
    #define Inf 0x3f3f3f3f
    
    using namespace std;
    
    struct node
    {
        int x, y;
        int step;
    } link_J[1040000], link_F[1040000], p, q;
    
    int n, m, a, b, fo, ft, u[104][104];
    bool v[104][104];
    char st[104][104];
    int jk[4][2] = {
       {
       0, 1}, {
       1, 0}, {
       0, -1}, {-1, 0}};
    
    void BFS();
    bool Judge(int dx, int dy);
    
    int main()
    {
        int T, i, j;
        scanf("%d", &T);
        while(T--)
        {
            fo = ft = 0;
            memset(v, true, sizeof(v));
            for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                    u[i][j] = Inf;
                }
            }
    
            scanf("%d %d", &n, &m);
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                for(j = 0; j < m; j++){
                    if(st[i][j] == 'F'){
                        v[i][j] = false;
                        u[i][j] = 0;
                        p.x = i, p.y = j, p.step = 0;
                        link_F[ft++] = p;
                    }
                    else if(st[i][j] == 'J'){
                        a = i, b = j;
                    }
                }
            }
            BFS();
        }
        return 0;
    }
    bool Judge(int dx, int dy)
    {
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
            return false;
        else
            return true;
    }
    void BFS()
    {
        int jo, jt, i, flag;
    
        while(fo < ft)
        {
            p = link_F[fo];
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    u[q.x][q.y] = q.step;
                    link_F[ft++] = q;
                }
            }
            fo++;
        }
    
        flag = 0, jo = jt = 0;;
        memset(v, true, sizeof(v));
        p.x = a;
        p.y = b;
        p.step = 0;
        if(p.x == 0 || p.x == n-1 || p.y == 0 || p.y == m-1)
        {
            flag = 1;
            printf("%d\n", p.step+1);
        }
        else if(p.step < u[p.x][p.y])
        {
            link_J[jt++] = p;
            v[p.x][p.y] = false;
        }
    
        while(jo < jt)
        {
            p = link_J[jo];
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && q.step < u[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    link_J[jt++] = q;
                    if(q.x == 0 || q.x == n-1 || q.y == 0 || q.y == m-1)
                    {
                        flag = 1;
                        printf("%d\n", q.step+1);
                        break;
                    }
                }
            }
            if(flag)
                break;
            jo++;
        }
        if(!flag)
            printf("IMPOSSIBLE\n");
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #define Inf 0x3f3f3f3f
    
    using namespace std;
    
    struct node
    {
        int x, y;
        int step;
    } link_J[1040000], link_F[1040000], p, q;
    
    int n, m, a, b, fo, ft, u[1004][1004];
    bool v[1004][1004];
    char st[1004][1004];
    int jk[4][2] = {
       {
       0, 1}, {
       1, 0}, {
       0, -1}, {-1, 0}};
    
    void BFS();
    bool Judge(int dx, int dy);
    
    int main()
    {
        int T, i, j;
        scanf("%d", &T);
        while(T--)
        {
            fo = ft = 0;
            memset(v, true, sizeof(v));
            for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                    u[i][j] = Inf;
                }
            }
    
            scanf("%d %d", &n, &m);
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                for(j = 0; j < m; j++){
                    if(st[i][j] == 'F'){
                        v[i][j] = false;
                        u[i][j] = 0;
                        p.x = i, p.y = j, p.step = 0;
                        link_F[ft++] = p;
                    }
                    else if(st[i][j] == 'J'){
                        a = i, b = j;
                    }
                }
            }
            BFS();
        }
        return 0;
    }
    bool Judge(int dx, int dy)
    {
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
            return false;
        else
            return true;
    }
    void BFS()
    {
        int jo, jt, i, flag;
    
        while(fo < ft)
        {
            p = link_F[fo];
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    u[q.x][q.y] = q.step;
                    link_F[ft++] = q;
                }
            }
            fo++;
        }
    
        flag = 0, jo = jt = 0;;
        memset(v, true, sizeof(v));
        p.x = a;
        p.y = b;
        p.step = 0;
        if(p.x == 0 || p.x == n-1 || p.y == 0 || p.y == m-1)
        {
            flag = 1;
            printf("%d\n", p.step+1);
        }
        else if(p.step < u[p.x][p.y])
        {
            link_J[jt++] = p;
            v[p.x][p.y] = false;
        }
    
        while(jo < jt)
        {
            p = link_J[jo];
            for(i = 0; i < 4; i++)
            {
                q.x = p.x + jk[i][0];
                q.y = p.y + jk[i][1];
                q.step = p.step + 1;
                if(Judge(q.x, q.y) && v[q.x][q.y] && q.step < u[q.x][q.y] && st[q.x][q.y] != '#')
                {
                    v[q.x][q.y] = false;
                    link_J[jt++] = q;
                    if(q.x == 0 || q.x == n-1 || q.y == 0 || q.y == m-1)
                    {
                        flag = 1;
                        printf("%d\n", q.step+1);
                        break;
                    }
                }
            }
            if(flag)
                break;
            jo++;
        }
        if(!flag)
            printf("IMPOSSIBLE\n");
    }

[vjudge]: https://vjudge.net/contest/162997#problem/I