41分TLE,QAQ
查看原帖
41分TLE,QAQ
220362
chenxuanting楼主2020/6/24 20:26
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
struct node
{
	int x,y;
};
vector<node> a[105][105];
int vis[105][105],light[105][105];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int ans;
void read(int &x)
{
	int fh=1;
	char s;
	x=0;
	s=getchar();
	if(s<'0'||s>'9'){
		if(s=='-'){
			fh=-1;
		} 
	}else{
		x=int(s-'0');
	}
	while(s=getchar()){
		if(s>='0'&&s<='9'){
			x*=10;
			x+=(int)(s-'0');
		}else{
			break;
		}
	}
	x*=fh;
}
void bfs()
{
	queue<node> q;
	q.push((node){1,1});
	while(!q.empty()){
		node cur=q.front();
		q.pop();
		if(light[cur.x][cur.y]==2){
			int tf=0;
			for(int i=0;i<4;i++){
				int nowx=cur.x+dx[i];
			    int nowy=cur.y+dy[i];
			    if(vis[nowx][nowy]==1){
			    	tf=1;
			    	break;
				}
			}
			if(tf==0){
				continue;
			}
		}
		light[cur.x][cur.y]=1;
		vis[cur.x][cur.y]=1;
		for(int i=0;i<a[cur.x][cur.y].size();i++){
			node now=a[cur.x][cur.y][i];
			if(vis[now.x][now.y]==1){
				continue;
			}
			light[now.x][now.y]=2;
			q.push(now);
		}
		for(int i=0;i<4;i++){
			int nowx=cur.x+dx[i];
			int nowy=cur.y+dy[i];
			if(nowx>n||nowy>n||vis[nowx][nowy]==1||light[nowx][nowy]==0){
				continue;
			}
			q.push((node){nowx,nowy});
		}
	}
}
int main()
{
	read(n);
	read(m);
	light[1][1]=1;
	for(int i=1;i<=m;i++){
		int x1,x2,y1,y2;
		read(x1);
		read(x2);
		read(y1);
		read(y2);
		a[x1][x2].push_back((node){y1,y2});
	}
	bfs();
	for(int i=1;i<=n;i++){
		for(int i1=1;i1<=n;i1++){
			if(light[i][i1]!=0){
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

这个代码主要是被卡住了(TLE了)

2020/6/24 20:26
加载中...