题解：P14273 [ROI 2014 Day1] 鲁滨逊与鳄鱼

做绿题红温了。

60tps做法

遍历可以走出岛上的鳄鱼，然后入队，最后 BFS 处理即可。但是时间复杂度

\mathcal{O}(n^2m^2)

，写出来肯定 TLE。

正解做法（30tps）

发现某些鳄鱼挡在一些鳄鱼的道路上，只有那些鳄鱼走了，这些鳄鱼才能走。所以可以建有向图，表示某些鳄鱼要在另一些鳄鱼走的前提下才能走。由于有些鳄鱼没有被挡，即没有前置，所以可以把它看做入度为 0 的点，然后就可以愉快地拓扑了。

但是可以发现，在最坏情况下几乎每只鳄鱼都有前置，所以可认为所有鳄鱼都有长度为

n

或

m

的前置，对其进行建边的空间复杂度大约为

\mathcal{O}(n^2m)

，已经超过了限制。

那怎么办呢？

100tps优化

发现在同一条道路上，若有一只沿着这个方向的鳄鱼可以走，那么其他同向鳄鱼在非同向鳄鱼走之后也一定可以走。

因为第一只沿着这个方向走的鳄鱼可以走代表着对于这只鳄鱼来说这个方向已经没有障碍物了，其余同向的鳄鱼只要移除非同向的鳄鱼就可以走了。

于是在加边的时候，若有第一只和自己方向一样的鳄鱼，则可以不用入边了。

此外，由于我的代码是用邻接表实现的，空间比链式前向星大，所以请开 short，因为最大也就 2000，要不然会 MLE 三个点。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,indeg[2001][2001];
char a[2001][2001]; 
vector< pair<short,short> > dep[2001][2001];
queue< pair<short,short> > q;
void solve(short x,short y){
	if(a[x][y]=='.') return;
	short xx=0,yy=0;
	if(a[x][y]=='N') xx=-1;
	else if(a[x][y]=='S') xx=1;
	else if(a[x][y]=='E') yy=1;
	else if(a[x][y]=='W') yy=-1;
	short nx=x+xx,ny=y+yy;
	while(nx>=1&&ny>=1&&nx<=n&&ny<=m){
		if(a[nx][ny]!='.'){
			dep[nx][ny].push_back({x,y});
			indeg[x][y]++;
		}
		if(a[nx][ny]==a[x][y]) break;
		nx+=xx;
		ny+=yy;
	}
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j) cin>>a[i][j];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j) solve(i,j);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]!='.'&&indeg[i][j]==0){
				q.push(make_pair(i,j));
				a[i][j]='.';
			}
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		ans++;
		for(int i=0;i<dep[x][y].size();++i){
			int xx=dep[x][y][i].first,yy=dep[x][y][i].second;
			indeg[xx][yy]--;
			if(a[xx][yy]!='.'&&indeg[xx][yy]==0){
				q.push(make_pair(xx,yy));
				a[xx][yy]='.';
			}
		}
	}
	cout<<ans;
    return 0;
}

说句闲话

如果鲁滨逊扔的坚果能惊动鳄鱼，经过计算，能发现这个坚果大约 5kg 到 10kg 左右。

请勿在现实生活中对鳄鱼进行此类测试！ 打扰野生动物是不道德且危险的。

题解：P14273 [ROI 2014 Day1] 鲁滨逊与鳄鱼

文章操作

60tps做法

正解做法（30tps）

100tps优化

AC Code：

说句闲话

相关推荐

评论

题解：P14273 [ROI 2014 Day1] 鲁滨逊与鳄鱼