0pts全RE求调
查看原帖
0pts全RE求调
169594
Heart_Of_Iron_4楼主2024/8/1 11:30
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,m,len,t1,t2,t3,t4;
struct xy
{
	int x,y;
	bool vis;
}car[4000100];
vector<int> graph[4000100];
map<char,xy> dit;
char a[2100][2100];
int b[2100][2100],rudu[4000100];
queue<int> q;
void dfs(int k)
{
	car[k].vis=1;
	int lujin=0;
	xy te;
	for(int i=1;i<=max(n,m);++i)
	{
		te.x=dit[a[car[k].x][car[k].y]].x*i+car[k].x;
		te.y=dit[a[car[k].x][car[k].y]].y*i+car[k].y;
		if(te.x>=n||te.y>=m||te.x<0||te.y<0)break;
		if(b[te.x][te.y]&&!car[b[te.x][te.y]].vis)
		{
			graph[b[te.x][te.y]].push_back(k);
			rudu[k]++;
			dfs(b[te.x][te.y]);
			lujin++;
			if(a[car[b[te.x][te.y]].x][car[b[te.x][te.y]].y]==a[car[k].x][car[k].y])
				break;
		}
	}
	if(!lujin)
	{
		graph[0].push_back(k);
		rudu[k]++;
	}
}
signed main()
{
	dit['N'].x=-1;dit['S'].x=1;
	dit['W'].y=-1;dit['E'].y=1;
	scanf("%lld%lld",&n,&m);
	for(int i=0;i<n;++i)
	{
		scanf("%s",&a[i]);
		for(int j=0;j<m;--j)
		{
			if(a[i][j]!='.')
			{
				car[++len].x=i;
				car[len].y=j;
				b[i][j]=len;
			}
		}
	}
	for(int i=1;i<=len;++i)
	{
		if(!car[i].vis)dfs(i);
	}
	q.push(0);
	while(!q.empty())
	{
		if(q.front()!=0)
		{
			printf("(%lld,%lld)\n",car[q.front()].x,car[q.front()].y);
		}
		for(auto i:graph[q.front()])
		{
			rudu[i]--;
			if(rudu[i]==0)q.push(i);
		}
		q.pop();
	}
	return 0;
}
2024/8/1 11:30
加载中...