提交记录 #72153

编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#72153	#1037. 膨胀的tyx	Accepted	100	3284 ms	47484 K	C++ 11 / 3.5 K	q3540555	2022-06-30 15:52:07

显示原始代码

/*#include <iostream>
#include <map>
#include <utility>
using namespace std;

bool success = 0;
int n, m;
int matrix[2000][2000];
pair<int, int> t0, t, t1;
map<pair<int, int>, pair<int, int>> res;

void Search(int x, int y, int rx, int ry);
int main(int argc, char** argv, char** env) {
    char tmp;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin.get(tmp);
            while (tmp == ' ' || tmp == '\n') cin.get(tmp);
            if (tmp == '#') {
                matrix[i][j] = 0;
                continue;
            }
            matrix[i][j] = 1;
            if (tmp == 'S') {
                t.first = i, t.second = j;
            }
        }
    }

    Search(t.first % n, t.second % m, t.first, t.second);

    if (success) {
        cout << "Yes";
        return 0;
    }
    cout << "No";
    return 0;
}

void Search(int x, int y, int rx, int ry) {
    if (matrix[x][y] == 0 || success)
        return;
    t.first = x, t.second = y, t1.first = rx, t1.second = ry;
    if (res[t] == t0)
        res[t] = t1;
    else if (res[t] != t1) {
        success = 1;
        return;
    } else
        return;

    Search((x + 1) % n, y, rx + 1, ry);
    if (x - 1 >= 0)
        Search((x - 1) % n, y, rx - 1, ry);
    else
        Search((x - 1) % n + n, y, rx - 1, ry);

    Search(x, (y + 1) % m, rx, ry + 1);

    if (y - 1 >= 0)
        Search(x, (y - 1) % m, rx, ry - 1);
    else
        Search(x, (y - 1) % m + m, rx, ry - 1);
}*/
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define spause() system("pause")

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> prdd;

const int dinf = 0x7fffffff;
const llong llinf = 0x7fffffffffffffff;
const int way[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

struct cao {
    bool vd;
    int dx = dinf, dy = dinf;
};

int n, m, ans = 0;
vector<prdd> bfsn, tmp;
cao ecao[2000][2000];

int pmd(int a, int p) {
    int ans = a % p;
    if (ans < 0)
        ans += p;
    return ans;
}

void bfsnp(prdd p) {
    for (int i = 0; i < 4; i++) {
        int nl = p.first + way[i][0], nr = p.second + way[i][1];
        if (!ecao[pmd(nl, n)][pmd(nr, m)].vd)
            continue;
        int nx = ecao[p.first][p.second].dx, ny = ecao[p.first][p.second].dy;
        if (nl < 0 || nr < 0 || nl >= n || nr >= m) {
            nx += way[i][0];
            ny += way[i][1];
        }
        if (ecao[pmd(nl, n)][pmd(nr, m)].dx == dinf) {
            tmp.push_back(prdd(pmd(nl, n), pmd(nr, m)));
            ecao[pmd(nl, n)][pmd(nr, m)].dx = nx;
            ecao[pmd(nl, n)][pmd(nr, m)].dy = ny;
        } else if (nx != ecao[pmd(nl, n)][pmd(nr, m)].dx || ny != ecao[pmd(nl, n)][pmd(nr, m)].dy) {
            bfsn.clear();
            tmp.clear();
            ans++;
        }
    }
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char tmp;
            cin >> tmp;
            if (tmp == '#')
                ecao[i][j].vd = false;
            else
                ecao[i][j].vd = true;
            if (tmp == 'S') {
                ecao[i][j].dx = ecao[i][j].dy = 0;
                bfsn.push_back(prdd(i, j));
            }
        }

    while (!bfsn.empty()) {
        for (int i = 0; i < bfsn.size(); i++) bfsnp(bfsn.at(i));
        bfsn = tmp;
        tmp.clear();
    }

    if (ans)
        printf("Yes");
    else
        printf("No");
    spause();
    return 0;
}

子任务 #1

Accepted

得分：100

测试点 #1

Accepted

得分：100

用时：20 ms

内存：47232 KiB

输入文件（data1.in）

3 3
#.#
#.#
#S#

答案文件（data1.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #2

Accepted

得分：100

用时：19 ms

内存：47220 KiB

输入文件（data2.in）

5 5
#.#.#
..#.S
#####
..#..
#.#.#

答案文件（data2.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #3

Accepted

得分：100

用时：19 ms

内存：47216 KiB

输入文件（data3.in）

7 4
.##.
.S##
#.##
#..#
##.#
.#..
.###

答案文件（data3.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #4

Accepted

得分：100

用时：19 ms

内存：47344 KiB

输入文件（data4.in）

5 5
#.#.#
..#..
#####
.S#..
#.#.#

答案文件（data4.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #5

Accepted

得分：100

用时：18 ms

内存：47328 KiB

输入文件（data5.in）

6 20
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
S.#..#..#..#..#..#..
##..#.
<36 bytes omitted>

答案文件（data5.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #6

Accepted

得分：100

用时：18 ms

内存：47224 KiB

输入文件（data6.in）

5 5
#.#.#
..#.S
#####
..#..
#.#.#

答案文件（data6.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #7

Accepted

得分：100

用时：20 ms

内存：47232 KiB

输入文件（data7.in）

3 3
#.#
#.#
#S#

答案文件（data7.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #8

Accepted

得分：100

用时：54 ms

内存：47304 KiB

输入文件（data8.in）

2000 2000
S#########################################################################################
<4001910 bytes omitted>

答案文件（data8.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #9

Accepted

得分：100

用时：159 ms

内存：47484 KiB

输入文件（data9.in）

2000 2000
S.........................................................................................
<4001910 bytes omitted>

答案文件（data9.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #10

Accepted

得分：100

用时：248 ms

内存：47440 KiB

输入文件（data10.in）

2000 2000
S.........................................................................................
<4001910 bytes omitted>

答案文件（data10.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #11

Accepted

得分：100

用时：231 ms

内存：47432 KiB

输入文件（data11.in）

2000 2000
S.........................................................................................
<4001910 bytes omitted>

答案文件（data11.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #12

Accepted

得分：100

用时：137 ms

内存：47332 KiB

输入文件（data12.in）

2000 2000
#S########################################################################################
<4001910 bytes omitted>

答案文件（data12.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #13

Accepted

得分：100

用时：141 ms

内存：47336 KiB

输入文件（data13.in）

2000 2000
##########################################################################################
<4001910 bytes omitted>

答案文件（data13.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #14

Accepted

得分：100

用时：139 ms

内存：47288 KiB

输入文件（data14.in）

2000 2000
##########################################################################################
<4001910 bytes omitted>

答案文件（data14.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #15

Accepted

得分：100

用时：140 ms

内存：47336 KiB

输入文件（data15.in）

2000 2000
##########################################################################################
<4001910 bytes omitted>

答案文件（data15.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #16

Accepted

得分：100

用时：19 ms

内存：47452 KiB

输入文件（data16.in）

5 5
##.##
##.##
#....
#S###
#..#.

答案文件（data16.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #17

Accepted

得分：100

用时：19 ms

内存：47356 KiB

输入文件（data17.in）

4 4
#.##
..#.
.#S#
#...

答案文件（data17.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #18

Accepted

得分：100

用时：145 ms

内存：47424 KiB

输入文件（data18.in）

2000 2000
#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
<4003911 bytes omitted>

答案文件（data18.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #19

Accepted

得分：100

用时：144 ms

内存：47332 KiB

输入文件（data19.in）

2000 2000
#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
<4003911 bytes omitted>

答案文件（data19.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #20

Accepted

得分：100

用时：128 ms

内存：47288 KiB

输入文件（data20.in）

2000 2000
#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
<4003911 bytes omitted>

答案文件（data20.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #21

Accepted

得分：100

用时：53 ms

内存：47328 KiB

输入文件（data21.in）

2000 2000
#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
<4003911 bytes omitted>

答案文件（data21.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #22

Accepted

得分：100

用时：147 ms

内存：47340 KiB

输入文件（data22.in）

2000 2000
#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
<4003911 bytes omitted>

答案文件（data22.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #23

Accepted

得分：100

用时：87 ms

内存：47336 KiB

输入文件（data23.in）

2000 2000
.#.###.##.#.#.###..#.#.#...##....##...#..#.#......##.###.##.#..##...##...########.###..#.
<4003911 bytes omitted>

答案文件（data23.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #24

Accepted

得分：100

用时：88 ms

内存：47292 KiB

输入文件（data24.in）

2000 2000
.#.###.##.#.#.###..#.#.#...##....##...#..#.#......##.###.##.#..##...##...########.###..#.
<4003911 bytes omitted>

答案文件（data24.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #25

Accepted

得分：100

用时：88 ms

内存：47320 KiB

输入文件（data25.in）

2000 2000
.#.###.##.#.#.###..#.#.#...##....##...#..#.#......##.###.##.#..##...##...########.###..#.
<4003911 bytes omitted>

答案文件（data25.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #26

Accepted

得分：100

用时：86 ms

内存：47320 KiB

输入文件（data26.in）

2000 2000
#.######..##.###..##...#...#.#.#...#.######.#.#######.#...##.#########..#.##.#...##.###.#
<4003911 bytes omitted>

答案文件（data26.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #27

Accepted

得分：100

用时：87 ms

内存：47296 KiB

输入文件（data27.in）

2000 2000
#.######..##.###..##...#...#.#.#...#.######.#.#######.#...##.#########..#.##.#...##.###.#
<4003911 bytes omitted>

答案文件（data27.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #28

Accepted

得分：100

用时：87 ms

内存：47304 KiB

输入文件（data28.in）

2000 2000
#.######..##.###..##...#...#.#.#...#.######.#.#######.#...##.#########..#.##.#...##.###.#
<4003911 bytes omitted>

答案文件（data28.out）

No

用户输出

No

系统信息

Exited with return code 0

测试点 #29

Accepted

得分：100

用时：214 ms

内存：47336 KiB

输入文件（data29.in）

2000 2000
.#...##...##....#.#....#.#.####..#.....###......##...#....##..##..#######...###.#.#.#...#
<4003911 bytes omitted>

答案文件（data29.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #30

Accepted

得分：100

用时：217 ms

内存：47368 KiB

输入文件（data30.in）

2000 2000
..##.....##..#.#..#..#.#..###....##.....#...#...........#.####......#..##.....###..#.#..#
<4003911 bytes omitted>

答案文件（data30.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #31

Accepted

得分：100

用时：218 ms

内存：47340 KiB

输入文件（data31.in）

2000 2000
###....#..........#.#.......####..#.#.#.#.##...####..##..##............#..#.##..#.#...##.
<4003911 bytes omitted>

答案文件（data31.out）

Yes

用户输出

Yes

系统信息

Exited with return code 0

测试点 #32

Accepted

得分：100

用时：75 ms

内存：47328 KiB

输入文件（data32.in）

2000 2000
..##...###.#.#...#..#.....#.#.....#....###.........##.##.....##...##..##.#......#........
<4003911 bytes omitted>

答案文件（data32.out）

No

用户输出

No

系统信息

Exited with return code 0