记一份像屎一样的代码

发布于 2020-11-17  106 次阅读


#include<bits/stdc++.h>
using namespace std;
struct node {
    char content = NULL;
    bool IsVisited = false;
    bool rIsVisited = false;
    int pos[5] = { -1,-1,-1,-1,-1 };
    int x = 0, y = 0;
};
int l[1001][1001];
int r[1001][1001];
node nmap[1001][1001];
queue<node> q;
void BFS(int x, int y) {
    int move[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
    nmap[x][y].IsVisited = true;
    memset(l, -1, sizeof(l));
    l[x][y] = 0;
    q.push(nmap[x][y]);
    node tnode;
    while (!q.empty()) {
        tnode = q.front();
        int tx = tnode.x, ty = tnode.y;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx, ny;
            nx = tx + move[i][0];
            ny = ty + move[i][1];
            if ((nmap[nx][ny].content == '.' || nmap[nx][ny].content == 'R' || nmap[nx][ny].content == 'Y') && !nmap[nx][ny].IsVisited) {
                nmap[nx][ny].IsVisited = true;
                l[nx][ny] = l[tx][ty] + 1;
                q.push(nmap[nx][ny]);
            }
        }
    }
}
void rBFS(int x, int y) {
    int move[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
    nmap[x][y].rIsVisited = true;
    memset(nmap[x][y].pos, 0, sizeof(nmap[x][y].pos));
    memset(r, -1, sizeof(r));
    r[x][y] = 1;
    q.push(nmap[x][y]);
    node tnode;
    while (!q.empty()) {
        tnode = q.front();
        int tx = tnode.x, ty = tnode.y;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx, ny;
            nx = tx + move[i][0];
            ny = ty + move[i][1];
            if ((nmap[nx][ny].content == '.' || nmap[nx][ny].content == 'R' || nmap[nx][ny].content == 'Y' || nmap[nx][ny].content == 'X') && !nmap[nx][ny].rIsVisited) {
                nmap[nx][ny].rIsVisited = true;
                //来的方向
                //if (move[i][0] == 1 && move[i][1] == 0) {
                //  nmap[nx][ny].pos = 1;//左
                //}
                //else if (move[i][0] == -1 && move[i][1] == 0) {
                //  nmap[nx][ny].pos = 2;//右
                //}
                //else if (move[i][0] == 0 && move[i][1] == 1) {
                //  nmap[nx][ny].pos = 3;//下
                //}
                //else if (move[i][0] == 0 && move[i][1] == -1) {
                //  nmap[nx][ny].pos = 4;//上
                //}
                //现在不知道当前点方向,只知道当前点和周围四个点相对位置,因为不知道谁是父节点,遍历周围四个点,谁方向一致且开销小认谁做爹
                //就算方向不一致开销也可能相同
                int dm = 0x3f3f3f3f, tdm = dm;
                //只要dm更新,就重置方向数组
                if ((nmap[nx][ny - 1].pos[1] == 1 || nmap[nx][ny - 1].pos[1] == 0) && nmap[nx][ny - 1].rIsVisited && r[nx][ny - 1] <= dm) {//左
                    nmap[nx][ny].pos[1] = 1;
                    r[nx][ny] = tdm = r[nx][ny - 1];
                    if (tdm < dm) {
                        memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                        nmap[nx][ny].pos[1] = 1;
                        dm = tdm;
                    }
                }
                if ((nmap[nx][ny + 1].pos[2] == 1 || nmap[nx][ny + 1].pos[2] == 0) && nmap[nx][ny + 1].rIsVisited && r[nx][ny + 1] <= dm) {//右
                    nmap[nx][ny].pos[2] = 1;
                    r[nx][ny] = tdm = r[nx][ny + 1];
                    if (tdm < dm) {
                        memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                        nmap[nx][ny].pos[2] = 1;
                        dm = tdm;
                    }
                }
                if ((nmap[nx - 1][ny].pos[3] == 1 || nmap[nx - 1][ny].pos[3] == 0) && nmap[nx - 1][ny].rIsVisited && r[nx - 1][ny] <= dm) {//上
                    nmap[nx][ny].pos[3] = 1;
                    r[nx][ny] = tdm = r[nx - 1][ny];
                    if (tdm < dm) {
                        memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                        nmap[nx][ny].pos[3] = 1;
                        dm = tdm;
                    }

                }
                if ((nmap[nx + 1][ny].pos[4] == 1 || nmap[nx + 1][ny].pos[4] == 0) && nmap[nx + 1][ny].rIsVisited && r[nx + 1][ny] <= dm) {//下
                    nmap[nx][ny].pos[4] = 1;
                    r[nx][ny] = tdm = r[nx + 1][ny];
                    if (tdm < dm) {
                        memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                        nmap[nx][ny].pos[4] = 1;
                        dm = tdm;
                    }

                }
                //四边有方向一致的
                //int dmin = 0x3f3f3f3f;
                //只有当方向一致过来大于等于转弯过来开销时,才能把两个方向都记下。
                //问题在于前面转过来开销方向也记下了,如果有更小的转过来的开销应当把前面的方向洗掉
                //两种转弯开销一样的情况是存在的,方向一致和转弯开销一致的情况也是存在的,所以不能洗光
                if (nmap[nx][ny - 1].rIsVisited == true && nmap[nx][ny - 1].pos[1] != 1) {
                    /*dmin = min(dmin, r[nx][ny - 1] + 1);
                    nmap[nx][ny].pos[1] = 1;*/
                    if (r[nx][ny - 1] + 1 <= dm) {
                        tdm = r[nx][ny - 1] + 1;
                        nmap[nx][ny].pos[1] = 1;
                        if (tdm < dm) {
                            memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                            nmap[nx][ny].pos[1] = 1;
                            dm = tdm;
                        }

                    }
                }
                if (nmap[nx][ny + 1].rIsVisited == true && nmap[nx][ny + 1].pos[2] != 1) {
                    if (r[nx][ny + 1] + 1 <= dm) {
                        tdm = r[nx][ny + 1] + 1;
                        nmap[nx][ny].pos[2] = 1;
                        if (tdm < dm) {
                            memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                            nmap[nx][ny].pos[2] = 1;
                            dm = tdm;
                        }

                    }
                }
                if (nmap[nx - 1][ny].rIsVisited == true && nmap[nx - 1][ny].pos[3] != 1) {
                    if (r[nx - 1][ny] + 1 <= dm) {
                        tdm = r[nx - 1][ny] + 1;
                        nmap[nx][ny].pos[3] = 1;
                        if (tdm < dm) {
                            memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                            nmap[nx][ny].pos[3] = 1;
                            dm = tdm;
                        }

                    }
                }
                if (nmap[nx + 1][ny].rIsVisited == true && nmap[nx + 1][ny].pos[4] != 1) {
                    if (r[nx + 1][ny] + 1 <= dm) {
                        tdm = r[nx + 1][ny] + 1;
                        nmap[nx][ny].pos[4] = 1;
                        if (tdm < dm) {
                            memset(nmap[nx][ny].pos, -1, sizeof(nmap[nx][ny].pos));
                            nmap[nx][ny].pos[4] = 1;
                            dm = tdm;
                        }
                    }
                }
                r[nx][ny] = dm;

                q.push(nmap[nx][ny]);
            }
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int sx, sy;//起点
        int rx, ry;//R点
        int ex, ey;//终点
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> nmap[i][j].content;
                nmap[i][j].x = i, nmap[i][j].y = j;
                nmap[i][j].IsVisited = false;
                nmap[i][j].rIsVisited = false;
                memset(nmap[i][j].pos, -1, sizeof(nmap[i][j].pos));
                if (nmap[i][j].content == 'X') {
                    sx = i, sy = j;
                }
                else if (nmap[i][j].content == 'Y') {
                    ex = i, ey = j;
                }
                else if (nmap[i][j].content == 'R') {
                    rx = i, ry = j;
                }
            }
        }
        BFS(sx, sy);
        int toend = l[ex][ey], tor = l[rx][ry];//走路去终点和狮鹫的开销
        int total = 0;
        if (toend == -1 || tor == -1) {//无法到终点或狮鹫
            total = toend;
        }
        else {
            //接下来获得狮鹫到终点所需开销(bfs)
            rBFS(rx, ry);
            int rtoend = r[ex][ey];
            total = min(toend, tor + rtoend);
        }

        cout << total << endl;
    }
    return 0;
}

希望代码量和阅读量上去了可以再也不要写这种shit一样的代码。


夢に僕らで帆を張って 来るべき日のために夜を越え。