\(\mathcal{Description}\)

在一张 \(n\times m\) 的网格图中有空格 . 和障碍格 #，\(q\) 次询问，每次查询从 \((x_1,y_1)\) 出发，是否能仅向下或向右走，在不经过障碍格的情况下走到 \((x_2,y_2)\)。

\(n,m\le500\)，\(q\le6\times10^5\)。

\(\mathcal{Solution}\)

Trick 向的分治解法。

不妨按行分治，设当前分治区间为 \([l,r]\)，取中点 \(p\)，则本层分治求解满足 \(l\le x_1\le p<x_2\le r\) 的所有询问（对于 \(x_1=x_2\) 的，特判即可）。记 \(f(i,j)\) 表示从 \((i,j)\) 出发，仅向下或向右走能到达的所有 \((p,k)\) 中 \(k\) 的集合（\(l\le i\le p\)）；对应地记 \(g(i,j)\) 表示从 \((i,j)\) 出发，仅向上或向左走能到达的所有 \((p,k)\) 中 \(k\) 的集合（\(p<i\le r\)）。用 std::bitset 维护转移就能快速求解。

复杂度 \(\mathcal O\left(\left(\frac{nm^2}{\omega}+q\right)\log n\right)\)。

\(\mathcal{Code}\)

/* Clearink */

#include <bitset>

#include <cstdio>

#include <vector>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

#define x1 my_x1

#define x2 my_x2

#define y1 my_y1

#define y2 my_y2

inline int rint() {

	int x = 0, f = 1, s = getchar();

	for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;

	for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );

	return x * f;

}

template<typename Tp>

inline void wint( Tp x ) {

	if ( x < 0 ) putchar( '-' ), x = -x;

	if ( 9 < x ) wint( x / 10 );

	putchar( x % 10 ^ '0' );

}

const int MAXN = 500, MAXQ = 6e5;

int n, m, q;

bool ans[MAXQ + 5];

char grid[MAXN + 5][MAXN + 5];

std::bitset<MAXN + 5> f[MAXN + 5][MAXN + 5];

struct Query { int x1, y1, x2, y2, id; };

std::vector<Query> allq;

inline void solve( const int l, const int r, const std::vector<Query>& qry ) {

	if ( qry.empty() ) return ;

	int mid = l + r >> 1;

	per ( i, m, 1 ) {

		if ( grid[mid][i] == '.' ) ( f[mid][i] = f[mid][i + 1] ).set( i );

		else f[mid][i].reset();

	}

	rep ( i, 1, m ) { // save data in f[0] temporarily.

		if ( grid[mid][i] == '.' ) ( f[0][i] = f[0][i - 1] ).set( i );

		else f[0][i].reset();

	}

	per ( i, mid - 1, l ) {

		per ( j, m, 1 ) {

			if ( grid[i][j] == '.' ) f[i][j] = f[i + 1][j] | f[i][j + 1];

			else f[i][j].reset();

		}

	}

	rep ( i, mid + 1, r ) {

		rep ( j, 1, m ) {

			if ( grid[i][j] == '.' ) {

				f[i][j] = f[i == mid + 1 ? 0 : i - 1][j] | f[i][j - 1];

			} else f[i][j].reset();

		}

	}

	if ( l == r ) {

		for ( auto q: qry ) ans[q.id] = f[l][q.y1].test( q.y2 );

		return ;

	}

	std::vector<Query> lefq, rigq;

	for ( auto q: qry ) {

		if ( q.x2 <= mid ) lefq.push_back( q );

		else if ( mid < q.x1 ) rigq.push_back( q );

		else ans[q.id] = ( f[q.x1][q.y1] & f[q.x2][q.y2] ).any();

	}

	solve( l, mid, lefq ), solve( mid + 1, r, rigq );

}

int main() {

	n = rint(), m = rint();

	rep ( i, 1, n ) scanf( "%s", grid[i] + 1 );

	allq.resize( q = rint() );

	rep ( i, 0, q - 1 ) {

		allq[i].x1 = rint(), allq[i].y1 = rint();

		allq[i].x2 = rint(), allq[i].y2 = rint();

		allq[i].id = i + 1;

	}

	solve( 1, n, allq );

	rep ( i, 1, q ) puts( ans[i] ? "Yes" : "No" );

	return 0;

}

巴特西

Solution -「CF 232E」Quick Tortoise

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章