I为什么卡50啊?

/*************************************************************************
    > File Name: i.cpp
    > Author: Haoming Bai
    > Mail: haomingbai@hotmail.com
    > Created Time: 2024年07月17日 星期三 09时24分27秒
 ************************************************************************/

#include <cstddef>
#include <iostream>
#include <string>

using namespace std;

unsigned long long record[1000][1000][4] = {0};

inline void fetch(int n, int m, int ***sto)
{
    // we define left as 0, right as 1, below as 2, above as 3, direction.
    char *tmp = new char[m + 5];
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        for (int j = 0; j < m; j++)
        {
            switch (tmp[j])
            {
            case '-':
                sto[i][j][0] = 0;
                sto[i][j][1] = 1;
                sto[i][j][2] = 3;
                sto[i][j][3] = 2;
                break;
            case '|':
                sto[i][j][0] = 1;
                sto[i][j][1] = 0;
                sto[i][j][2] = 2;
                sto[i][j][3] = 3;
                break;
            case '/':
                sto[i][j][0] = 2;
                sto[i][j][1] = 3;
                sto[i][j][2] = 0;
                sto[i][j][3] = 1;
                break;
            case '\\':
                sto[i][j][0] = 3;
                sto[i][j][1] = 2;
                sto[i][j][2] = 1;
                sto[i][j][3] = 0;
                break;
            }
        }
    }
    delete[] tmp;
}

template <typename T> inline T ***gendynamicarr_3d(size_t n, size_t m, size_t k)
{
    // we define left as 0, right as 1, below as 2, above as 3, direction.
    T ***res = new T **[n];
    res[0] = new T *[n * m];
    res[0][0] = new T[n * m * k]();
    for (size_t i = 1; i < m; i++)
    {
        res[0][i] = res[0][i - 1] + k;
    }
    for (size_t i = 1; i < n; i++)
    {
        res[i] = res[i - 1] + m;
        for (size_t j = 0; j < m; j++)
        {
            res[i][j] = res[i - 1][j] + (k * m);
        }
    }
    return res;
}

unsigned long long solve(int row, int column, int dir, int n, int m, int r_ori, int c_ori, int dir_ori, int ***dat,
                         bool ***flag = nullptr, bool **affected = nullptr)
{
    if (record[r_ori][c_ori][dir_ori] && row == r_ori && column == c_ori && dir == dir_ori)
    {
        return record[r_ori][c_ori][dir_ori];
    }
    int f = 0, a = 0;
    // cout << row << ' ' << column << ' ' << dir << ' ' << dat[row][column][dir] << endl;
    // we define left as 0, right as 1, below as 2, above as 3, direction.
    if (flag == nullptr || flag == NULL)
    {
        flag = gendynamicarr_3d<bool>(n, m, 4);
        f = 1;
    }
    if (affected == NULL || affected == nullptr)
    {
        affected = new bool *[n];
        affected[0] = new bool[m * n]();
        for (auto i = 1; i < n; i++)
        {
            affected[i] = affected[i - 1] + m;
        }
        a = 1;
    }
    // cout << flag[row][column][dir] << endl;
    if (flag[row][column][dir])
    {
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
        }
        return 0;
    }
    if (column >= m - 1 && dat[row][column][dir] == 1)
    {
        if (!(dat[row][column][dir] == dir) && !affected[row][column])
        {
            affected[row][column] = 1;
            if (f)
            {
                delete[] flag[0][0];
                delete[] flag[0];
                delete[] flag;
            }
            if (a)
            {
                delete[] affected[0];
                delete[] affected;
            }
            return 1;
        }
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
        }
        return 0;
    }
    if (row >= n - 1 && dat[row][column][dir] == 2)
    {
        if (!(dat[row][column][dir] == dir) && !affected[row][column])
        {
            affected[row][column] = 1;
            if (f)
            {
                delete[] flag[0][0];
                delete[] flag[0];
                delete[] flag;
            }
            if (a)
            {
                delete[] affected[0];
                delete[] affected;
            }
            return 1;
        }
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
        }
        return 0;
        // return !(dat[row][column][dir] == dir);
    }
    if (column <= 0 && dat[row][column][dir] == 0)
    {
        if (!(dat[row][column][dir] == dir) && !affected[row][column])
        {
            affected[row][column] = 1;
            if (f)
            {
                delete[] flag[0][0];
                delete[] flag[0];
                delete[] flag;
            }
            if (a)
            {
                delete[] affected[0];
                delete[] affected;
            }
            return 1;
        }
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
        }
        return 0;
        // return !(dat[row][column][dir] == dir);
    }
    if (row <= 0 && dat[row][column][dir] == 3)
    {
        if (!(dat[row][column][dir] == dir) && !affected[row][column])
        {
            affected[row][column] = 1;
            if (f)
            {
                delete[] flag[0][0];
                delete[] flag[0];
                delete[] flag;
            }
            if (a)
            {
                delete[] affected[0];
                delete[] affected;
            }
            return 1;
        }
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
        }
        return 0;
        // return !(dat[row][column][dir] == dir);
    }
    // cout << dir_ori << endl;
    // we define left as 0, right as 1, below as 2, above as 3, direction.
    int dir_next(dat[row][column][dir]), c_next(column), r_next(row);
    if (dir + dir_next == 5 || dir + dir_next == 1)
    {
        flag[row][column][dir] = 1;
        unsigned long long x = 1;
        int r = r_ori, c = c_ori;
        int d;
        if (dir_ori == 2 || dir_ori == 3)
        {
            d = 5 - dir_ori;
        }
        else
        {
            d = 1 - dir_ori;
        }
        switch (d)
        {
        case 0:
            c--;
            break;
        case 1:
            c++;
            break;
        case 2:
            r++;
            break;
        case 3:
            r--;
            break;
        }
        // cout << r << ' ' << c << ' ' << dir_ori << endl;
        if (affected[row][column])
        {
            x--;
        }
        else
        {
            affected[row][column] = 1;
        }
        if (c >= m || r >= n || r < 0 || c < 0)
        {
            if (f)
            {
                delete[] flag[0][0];
                delete[] flag[0];
                delete[] flag;
            }
            if (a)
            {
                delete[] affected[0];
                delete[] affected;
            }
            return x;
        }
        unsigned long long rr = solve(r, c, d, n, m, r, c, d, dat, flag, affected) + x;
        if (f)
        {
            delete[] flag[0][0];
            delete[] flag[0];
            delete[] flag;
        }
        if (a)
        {
            delete[] affected[0];
            delete[] affected;
            // record[row][column][dir] = rr;
        }
        if (row == r_ori && column == c_ori && dir == dir_ori)
        {
            record[r_ori][c_ori][dir_ori] = rr;
        }
        return rr;
    }
    else if (dir_next == 0)
    {
        c_next--;
    }
    else if (dir_next == 1)
    {
        c_next++;
    }
    else if (dir_next == 2)
    {
        r_next++;
    }
    else if (dir_next == 3)
    {
        r_next--;
    }
    flag[row][column][dir] = 1;
    // int res = solve(r_next, c_next, dir_next, n, m, dat, flag); //+ !(dat[row][column][dir] == dir);
    unsigned long long res = solve(r_next, c_next, dir_next, n, m, r_ori, c_ori, dir_ori, dat, flag, affected);
    unsigned long long judge = 0;
    if (!(dat[row][column][dir] == dir) && !affected[row][column])
    {
        affected[row][column] = 1;
        judge = 1;
    }
    res += judge;
    if (f)
    {
        delete[] flag[0][0];
        delete[] flag[0];
        delete[] flag;
    }
    if (a)
    {
        delete[] affected[0];
        delete[] affected;
    }
    if (row == r_ori && column == c_ori && dir == dir_ori)
    {
        record[r_ori][c_ori][dir_ori] = res;
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    // create an array of two dimension s.t. we can make it convenient to mark the route of light.
    // create an array of three dimension s.t. we can make_clear the property of mirrors.
    // create an array to store the result.
    // we define left as 0, right as 1, below as 2, above as 3, direction.
    int ***mirror = gendynamicarr_3d<int>(n, m, 4); // n * m * 4
    // unsigned long long ***result = gendynamicarr_3d<unsigned long long>(n, m, 4);
    fetch(n, m, mirror);
    int time;
    cin >> time;
    while (time--)
    {
        string a;
        int r, c, dir;
        cin >> r >> c >> a;
        r--, c--;
        if (a == "left")
        {
            dir = 0;
        }
        else if (a == "right")
        {
            dir = 1;
        }
        else if (a == "below")
        {
            dir = 2;
        }
        else
        {
            dir = 3;
        }
        switch (dir)
        {
        case 0:
            c--;
            break;
        case 1:
            c++;
            break;
        case 2:
            r++;
            break;
        case 3:
            r--;
            break;
        }
        if (c >= m || r >= n || r < 0 || c < 0)
        {
            cout << 0 << '\n';
            continue;
        }
        // cout << r << ' ' << c << endl;
        // cout << dir << endl;
        cout << solve(r, c, dir, n, m, r, c, dir, mirror) << '\n';
    }
}

如果去掉record数组会在53%的地方被超时,但是加上record会在50%被结果错误。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 14:32
点赞 评论 收藏
分享
06-20 21:22
已编辑
门头沟学院 Java
纯真的河老师在喝茶:答应了就跑啊,实习随便跑啊,别被pua了,md就是找个廉价劳动力,还平稳过度正式工,到时候跟你说没转正
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务