求助!请问为什么第9个测试点的字符不能完全输入进去
查看原帖
求助!请问为什么第9个测试点的字符不能完全输入进去
145577
Y_F_k_楼主2020/10/18 22:40
#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:40
加载中...