P1363-幻象迷宫

╰半橙微兮° 2023-06-01 08:52 11阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 typedef long long ll;
     4 using namespace std;
     5 struct point
     6 {
     7     int x;
     8     int y;
     9     bool operator == (point b)
    10     {
    11         return this->x==b.x && this->y==b.y;
    12     }
    13 };
    14 typedef pair<point,point> pir;
    15 
    16 inline ll read()
    17 {
    18     ll ans = 0;
    19     char ch = getchar(), last = ' ';
    20     while(!isdigit(ch)) last = ch, ch = getchar();
    21     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    22     if(last == '-') ans = -ans;
    23     return ans;
    24 }
    25 inline void write(ll x)
    26 {
    27     if(x < 0) x = -x, putchar('-');
    28     if(x >= 10) write(x / 10);
    29     putchar(x % 10 + '0');
    30 }
    31 
    32 int N,M;
    33 char m[1504][1504];
    34 bool vis[1504][1504];
    35 point pre[1504][1504];
    36 
    37 point st;
    38 int dx[] = {
        1,-1,0,0};
    39 int dy[] = {
        0,0,1,-1};
    40 bool bfs()
    41 {
    42     queue<pir> q;
    43     q.push({st,st});
    44     vis[st.x][st.y] = 1;
    45     pre[st.x][st.y] = st;
    46     while(!q.empty())
    47     {
    48         pir cur = q.front();q.pop();
    49         point a = cur.first;
    50         point b = cur.second;
    51 
    52         _for(i,0,4)
    53         {
    54             point ta;
    55             ta.x = (a.x+dx[i]+N)%N;
    56             ta.y = (a.y+dy[i]+M)%M;
    57             point tb;
    58             tb.x = b.x+dx[i];
    59             tb.y = b.y+dy[i];
    60 
    61             if(vis[ta.x][ta.y] && !(tb==pre[ta.x][ta.y]))
    62                 return true;
    63 
    64             if(vis[ta.x][ta.y] || m[ta.x][ta.y]=='#')
    65                 continue;
    66 
    67             vis[ta.x][ta.y] = 1,pre[ta.x][ta.y] = tb;
    68             q.push({ta,tb});
    69         }
    70     }
    71     return false;
    72 }
    73 int main()
    74 {
    75     while(scanf("%d%d",&N,&M)!=EOF)
    76     {
    77         memset(m,0,sizeof(m));
    78         memset(vis,0,sizeof(vis));
    79         memset(pre,0,sizeof(pre));
    80         _for(i,0,N)
    81         _for(j,0,M)
    82         {
    83             cin >> m[i][j];
    84             if(m[i][j]=='S')
    85                 st.x = i,st.y = j,m[i][j] = '.';
    86         }
    87 
    88         if(bfs())
    89             printf("Yes\n");
    90         else
    91             printf("No\n");
    92     }
    93     return 0;
    94 }

https://www.luogu.org/blog/Asurudo/solution-p1363

转载于:https://www.cnblogs.com/Asurudo/p/11366684.html