题解：P2130 狂奔的Wzf

solution

判断有无障碍的时候不需要以此枚举，利用前缀和，如果前缀为零证明没有障碍。

重复很多，写的很丑了，#3死活不过

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstdlib>

using namespace std;

int n,m;

const int N = 1100;

char s[N][N];

int zkx[N][N],sky[N][N],map[N][N];

int bfs() {

	queue<pair<int,int> > q;

	q.push(make_pair(1,1));

	while(!q.empty()) {

		int x=q.front().first,y=q.front().second;q.pop();

		for(int j=0;y+(1<<j)<=m;j++) {

			int tx=x,ty=y+(1<<j);

			if(sky[tx][ty]-sky[x][y-1]) break;

			if(map[tx][ty]) continue;

			if(s[tx][ty]=='#') {printf("%d",map[x][y]+1);exit(0);}

			map[tx][ty]=map[x][y]+1;q.push(make_pair(tx,ty));

		}

		for(int j=0;y-(1<<j)>=1;j++) {

			int tx=x,ty=y-(1<<j);

			if(sky[x][y]-sky[tx][ty-1]) break;

			if(map[tx][ty]) continue;

			if(s[tx][ty]=='#') {printf("%d",map[x][y]+1);exit(0);}

			map[tx][ty]=map[x][y]+1;q.push(make_pair(tx,ty));

		}

		for(int j=0;x+(1<<j)<=n;j++) {

			int tx=x+(1<<j),ty=y;

			if(zkx[tx][ty]-zkx[x-1][y]) break;

			if(map[tx][ty]) continue;

			if(s[tx][ty]=='#') {printf("%d",map[x][y]+1);exit(0);}

			map[tx][ty]=map[x][y]+1;q.push(make_pair(tx,ty));

		}

		for(int j=0;x-(1<<j)>=1;j++) {

			int tx=x-(1<<j),ty=y;

			if(zkx[x][y]-zkx[tx-1][ty]) break;

			if(map[tx][ty]) continue;

			if(s[tx][ty]=='#') {printf("%d",map[x][y]+1);exit(0);}

			map[tx][ty]=map[x][y]+1;q.push(make_pair(tx,ty));

		}

	}

}

int main() {

	cin>>n>>m;

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			char c;cin>>c;

			s[i][j]=c;

		}

	}

	if(s[1][1]=='#') return puts("0"),0;

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sky[i][j]=sky[i][j-1]+(s[i][j]=='#'||s[i][j]=='$'?0:1);

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) zkx[i][j]=zkx[i-1][j]+(s[i][j]=='#'||s[i][j]=='$'?0:1);

	bfs();cout<<-1;

	return 0;

}

巴特西

题解：P2130 狂奔的Wzf

solution

最新文章

热门文章