XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20798 #1037. 膨胀的tyx Accepted 100 3446 ms 35768 K C++ / 1.4 K kong 2019-08-08 16:11:00
显示原始代码 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

class Point {
public:
    int x, y;
    Point(int i, int j) : x(i), y(j) {}
    Point() {}
    friend bool operator==(const Point &A, const Point &B) { return (A.x == B.x && A.y == B.y); }
    friend bool operator!=(const Point &A, const Point &B) { return !(A == B); }
};

bool bfs(Point st);
bool is_legal(int x, int y);

const int dx[4] = { 1, -1, 0, 0 };
const int dy[4] = { 0, 0, 1, -1 };
const Point NPT = Point(-1, -1);
const int MAX = 2005;
char maze[MAX][MAX];
Point from[MAX][MAX];
int n, m;

bool bfs(Point st) {
    queue<Point> q;
    q.push(st);
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ax = p.x + dx[i], ay = p.y + dy[i];
            int rx = ax, ry = ay;
            rx = ((rx % n) + n) % n;
            ry = ((ry % m) + m) % m;
            if (maze[rx][ry] == '#')
                continue;
            if (from[rx][ry] == NPT) {
                from[rx][ry] = Point(ax, ay);
                q.push(Point(ax, ay));
            } else if (from[rx][ry] != Point(ax, ay))
                return true;
        }
    }
    return false;
}

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(from, -1, sizeof(from));
        for (int i = 0; i < n; i++) scanf("%s", maze[i]);
        Point st;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == 'S')
                    st = Point(i, j);
            }
        bool flag = bfs(st);
        if (flag)
            cout << "Yes";
        else
            cout << "No";
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：31 ms
内存：31812 KiB

输入文件（data1.in） 

3 3
#.#
#.#
#S#

答案文件（data1.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：25 ms
内存：31828 KiB

输入文件（data2.in） 

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

答案文件（data2.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：24 ms
内存：31736 KiB

输入文件（data3.in） 

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

答案文件（data3.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：23 ms
内存：31840 KiB

输入文件（data4.in） 

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

答案文件（data4.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：24 ms
内存：31828 KiB

输入文件（data5.in） 

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

答案文件（data5.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：37 ms
内存：31832 KiB

输入文件（data6.in） 

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

答案文件（data6.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：26 ms
内存：31828 KiB

输入文件（data7.in） 

3 3
#.#
#.#
#S#

答案文件（data7.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：41 ms
内存：35704 KiB

输入文件（data8.in） 

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

答案文件（data8.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：180 ms
内存：35764 KiB

输入文件（data9.in） 

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

答案文件（data9.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：328 ms
内存：35664 KiB

输入文件（data10.in） 

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

答案文件（data10.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：282 ms
内存：35768 KiB

输入文件（data11.in） 

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

答案文件（data11.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：132 ms
内存：35708 KiB

输入文件（data12.in） 

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

答案文件（data12.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：130 ms
内存：35668 KiB

输入文件（data13.in） 

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

答案文件（data13.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：146 ms
内存：35628 KiB

输入文件（data14.in） 

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

答案文件（data14.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：134 ms
内存：35704 KiB

输入文件（data15.in） 

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

答案文件（data15.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：23 ms
内存：31824 KiB

输入文件（data16.in） 

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

答案文件（data16.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：22 ms
内存：31828 KiB

输入文件（data17.in） 

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

答案文件（data17.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：159 ms
内存：35668 KiB

输入文件（data18.in） 

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

答案文件（data18.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：167 ms
内存：35668 KiB

输入文件（data19.in） 

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

答案文件（data19.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：182 ms
内存：35664 KiB

输入文件（data20.in） 

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

答案文件（data20.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：41 ms
内存：35704 KiB

输入文件（data21.in） 

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

答案文件（data21.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：165 ms
内存：35704 KiB

输入文件（data22.in） 

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

答案文件（data22.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：40 ms
内存：35636 KiB

输入文件（data23.in） 

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

答案文件（data23.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：45 ms
内存：35704 KiB

输入文件（data24.in） 

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

答案文件（data24.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：39 ms
内存：35704 KiB

输入文件（data25.in） 

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

答案文件（data25.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：42 ms
内存：35668 KiB

输入文件（data26.in） 

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

答案文件（data26.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：39 ms
内存：35668 KiB

输入文件（data27.in） 

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

答案文件（data27.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：40 ms
内存：35668 KiB

输入文件（data28.in） 

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

答案文件（data28.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：281 ms
内存：35740 KiB

输入文件（data29.in） 

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

答案文件（data29.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：288 ms
内存：35648 KiB

输入文件（data30.in） 

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

答案文件（data30.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #31
Accepted
得分：100
用时：270 ms
内存：35704 KiB

输入文件（data31.in） 

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

答案文件（data31.out） 

Yes

用户输出 

Yes

系统信息 

Exited with return code 0
测试点 #32
Accepted
得分：100
用时：40 ms
内存：35704 KiB

输入文件（data32.in） 

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

答案文件（data32.out） 

No

用户输出 

No

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号