求助P4082!请问为什么第9个测试点的字符不能完全输入进去
  • 板块学术版
  • 楼主Y_F_k_
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/10/18 22:44
  • 上次更新2023/11/5 10:26:01
查看原帖
求助P4082!请问为什么第9个测试点的字符不能完全输入进去
145577
Y_F_k_楼主2020/10/18 22:44
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int begin_a,begin_b,end_a,end_b;
int deep,tp,cnt;
int dfn[5000020],low[5000020];
int _stack[5000020];
vector <int> G[5000020];
vector <int> T[5000020];
char c[1520][1520];
bool p[1520][1520][4];
bool dis[1520][1520];
int fa[5000020];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int read()
{
    char ch=getchar();
    int s=0,w=1;
    while (ch<'0'||ch>'9')
    {
        if (ch=='-')
        {
            w=-1;
        }
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        s=(s<<1)+(s<<3)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int tra(int x,int y)
{
    return (x-1)*m+y;
}
int bk1(int x)
{
    return (x-1)/m+1;
}
int bk2(int x)
{
    int y=(x-1)/m+1;
    return x-(y-1)*m;
}
void dfs(int u,int f)
{
    fa[u]=f;
    for (int i=0;i<T[u].size();i++)
    {
        if (T[u][i]!=f)
        {
            dfs(T[u][i],u);
        }
    }
    return;
}
void CST(int u)
{
    dfn[u]=low[u]=++deep;
    _stack[++tp]=u;
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (dfn[v]==0)
        {
            CST(v);
            low[u]=min(low[u],low[v]);
            if (low[v]==dfn[u])
            {
                ++cnt;
                for (int j=0;j!=v;--tp)
                {
                    j=_stack[tp];
                    T[cnt].push_back(j);
                    T[j].push_back(cnt);
                }
                T[cnt].push_back(u);
                T[u].push_back(cnt);
            }
        }
        else
        {
            low[u]=min(low[u],dfn[v]);  
        }
    }
    return;
}
void BFS(int x,int y)
{
    queue<int> q;
    q.push(tra(x,y));
    dis[x][y]=1;
    while (!q.empty())
    {
        int u=bk1(q.front()),v=bk2(q.front());
        q.pop();
        for (int i=0;i<4;i++)
        {
            int a=u+dx[i],b=v+dy[i];
            if(a>=1&&a<=n&&b>=1&&b<=m&&c[a][b]=='.'&&!dis[a][b])
            {
                dis[a][b]=1;
                q.push(tra(a,b));
            }
        }
    }
}
bool check(int x,int y,int z)
{
    if (fa[x]==fa[y]) return 1;
    if (fa[fa[x]]==z&&fa[fa[y]]==z) return 0;
    if (fa[fa[x]]==z&&fa[fa[z]]==y) return 0;
    if (fa[fa[z]]==x&&fa[fa[y]]==z) return 0;
    if (fa[fa[z]]==fa[fa[x]]&&fa[fa[y]]==z) return 0;
    if (fa[fa[z]]==fa[fa[y]]&&fa[fa[x]]==z) return 0;
    return 1;
}
struct node
{
    int x_,y_;
};
int main()
{
    n=read();m=read();q=read();
    cnt=n*m;
    for (int i=1;i<=n;i++)
    {
        scanf("%s",c[i]+1);
        for (int j=1;j<=m;j++)
        {
            if (c[i][j]=='A'||c[i][j]=='.'||c[i][j]=='B')
            {
                if (c[i-1][j]=='A'||c[i-1][j]=='.'||c[i-1][j]=='B')
                {
                    G[tra(i,j)].push_back(tra(i-1,j));
                    G[tra(i-1,j)].push_back(tra(i,j));
                }
                if (c[i][j-1]=='A'||c[i][j-1]=='.'||c[i][j-1]=='B')
                {
                    G[tra(i,j)].push_back(tra(i,j-1));
                    G[tra(i,j-1)].push_back(tra(i,j));
                }
            }
            if (c[i][j]=='A') begin_a=i,begin_b=j;
            if (c[i][j]=='B') end_a=i,end_b=j;
        }
    }
//  cout<<"ff"<<endl;
    CST(tra(begin_a,begin_b));
    dfs(tra(begin_a,begin_b),0);
    BFS(begin_a,begin_b);
    queue<node> Q;
    if (dis[end_a][end_b-1]) p[end_a][end_b][0]=1,Q.push(node{tra(end_a,end_b),0});
    if (dis[end_a][end_b+1]) p[end_a][end_b][1]=1,Q.push(node{tra(end_a,end_b),1});
    if (dis[end_a-1][end_b]) p[end_a][end_b][2]=1,Q.push(node{tra(end_a,end_b),2});
    if (dis[end_a+1][end_b]) p[end_a][end_b][3]=1,Q.push(node{tra(end_a,end_b),3});
    while (!Q.empty())
    {
        int u=bk1(Q.front().x_),v=bk2(Q.front().x_);
        int w=Q.front().y_;
        Q.pop();
        int x=u-dx[w],y=v-dy[w];
        if (x>=1&&x<=n&&y>=1&&y<=m&&c[x][y]!='#'&&p[x][y][w]==0)
        {
            p[x][y][w]=1;
            Q.push(node{tra(x,y),w});
        }
        for (int i=0;i<4;i++)
        {
            if (p[u][v][i]==0&&i!=w&&check(tra(u+dx[w],v+dy[w]),tra(u+dx[i],v+dy[i]),tra(u,v))==1&&c[u+dx[i]][v+dy[i]]!='#'&&u+dx[i]>=1&&u+dx[i]<=n&&v+dy[i]>=1&&v+dy[i]<=m)
            {
                p[u][v][i]=1;
                Q.push(node{tra(u,v),i});
            }
        }
    }
    while (q--)
    {
        int a1,a2;
        a1=read();
        a2=read();
        if (c[a1][a2]=='B'||p[a1][a2][0]||p[a1][a2][1]||p[a1][a2][2]||p[a1][a2][3])
        {
            cout<<"YES"<<endl;
        }
        else cout<<"NO"<<endl;
    }
    return 0;
}
2020/10/18 22:44
加载中...