题意与分析（CodeForces 540C）

这题坑惨了我。。。。我和一道经典的bfs题混淆了，这题比那题简单。

那题大概是这样的，一个冰塔，第一次踩某块会碎，第二次踩碎的会掉落。然后求可行解。

但是这题。。。是冰塔的一层

也就是说，它只是个稍微有点限制的二维迷宫问题。

后面就好理解了，不过需要考虑下这种数据：

这种数据答案是no。解决的方法可以考虑这样：分成两个数组来记录访问状态：vis数组和block数组。

代码

#include <queue>

#include <set>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

bool iscracked[505][505];

bool vis[505][505];

set<pair<int,int> > s;

int bx,by,ex,ey,n,m;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

bool bfs()

{

	queue<pair<int,int> > q;

	q.push(MP(bx,by));

	s.insert(MP(bx,by));

	iscracked[bx][by]=true;

	auto end_pair=MP(ex,ey);

	while(!q.empty())

	{

		auto now=q.front(); q.pop();

		if(now==end_pair && iscracked[now.fi][now.se] && vis[now.fi][now.se]) return true;

		//cout<<"NP: "<<now.fi<<" "<<now.se<<endl;

		iscracked[now.fi][now.se]=true;

		vis[now.fi][now.se]=true;

		rep(i,0,3)

		{

			int tx=now.fi+dx[i], ty=now.se+dy[i];

			if(tx>=1 && tx<=n && ty>=1 && ty<=m && (!iscracked[tx][ty]||(tx==ex&&ty==ey)))

			{

				auto tstat=MP(tx,ty);

				//cout<<"Trying to go"<<tx<<" "<<ty<<" "<<iscracked[tx][ty]<<endl;

				if(s.find(tstat)==s.end() || tstat==end_pair)

				{

					//cout<<"    success"<<endl;

					s.insert(tstat);

					q.push(tstat);

				}

			}

		}

	}

	return false;

}

int main()

{

	cin>>n>>m;

	ZERO(iscracked);ZERO(vis);

	rep(i,1,n)

	{

		string str; cin>>str;

		rep(j,0,m-1)

		{

			iscracked[i][j+1]=vis[i][j+1]=str[j]=='X';

		}

	}

	cin>>bx>>by>>ex>>ey;

	vis[bx][by]=false;

	//if(bx==ex && by==ey && n==1 && m==1)

	cout<<string(bfs()?"YES":"NO")<<endl;

	return 0;

}

巴特西

「日常训练」Ice Cave（Codeforces Round 301 Div.2 C）

题意与分析（CodeForces 540C）

代码

最新文章

热门文章