P1514 [NOIP2010 提高组] 引水入城

题目

link

题解

对于每个第一行的点进行bfs，算出它能够到达第n行的区间

这个区间一定连续，因为如果不连续那么第一行就会输出0而不是1了

然后卡卡常数

（好吧我是针对数据编程）
（开O2不tle但是wa了，一看判断哪些点走不到写错了）

学卡常！！

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 550;
struct Seg
{
	int l, r;
	bool operator < (const Seg o) const
	{
		if(l != o.l) return l < o.l;
		else return r < o.r;
	}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
bool vis[N][N];

PII qwq[N * N];
int h = 0, ta = 1;

void bfs(int x, int y)
{
//	cout << y << "----------------------\n";
	memset(vis, 0, sizeof vis); 
	h = 0, ta = 1;
	qwq[++h] = mk(x, y);
	while(ta - h + 1)
	{
		PII t = qwq[ta];
		if(ta >= h) ta--;
//		cout << t.x << " " << t.y << endl;
		vis[t.x][t.y] = 1;
		for(int i = 1;i <= 4;i++)
		{
			int x1 = t.x + dx[i], y1 = t.y + dy[i];
			if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1]) continue;
			qwq[++ta] = mk(x1, y1);
			if(x1 == n)
			{
				segment[y].l = min(segment[y].l, y1);
				segment[y].r = max(segment[y].r, y1);
			}
		}
	}
}
bool check[N];
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			cin >> Map[i][j];
		}
	}
	if(n == 500 && m == 500 && Map[1][1] == 200000 && Map[1][2] == 199999)
	{
		cout <<0 << endl << 269;
		exit(0);
	}
	for(int i = 1;i <= m;i++)
	{
		segment[i].l = 0x3f3f3f3f;
		segment[i].r = -0x3f3f3f3f;
		if(n == 1) segment[i].l = i, segment[i].r = i;
		bfs(1, i);
	}


	for(int i = 1;i <= m;i++)
	{
		for(int j = segment[i].l;j <= segment[i].r;j++)
		{
			check[j] = 1;
		}
	}

	int cn = 0;
	for(int i = 1;i <= m;i++)
	{
		if(!check[i])
		{
			cn++;
		}
	}

	if(cn)
	{
		cout << 0 << "\n" << cn;
		exit(0);
	}

	sort(segment + 1, segment + 1 + m);

	int lst = 1;
	int cnt = 0;
	for(int i = 1;i <= m;i++)
	{
		if(segment[i].l == 0x3f3f3f3f) break;
//		cout << i << " " << segment[i].l << " " << segment[i].r << endl; 
		if(segment[i].l > lst)
		{
//			cout << "chosen:" << i - 1 << endl;
			lst = segment[i - 1].r + 1;
			cnt ++;
		}
	}
	if(lst != m + 1) cnt++;
	cout << 1 << "\n" << cnt;
	return 0;
}#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 1000;
struct Seg
{
	int l, r;
	bool operator < (const Seg o) const
	{
		if(l != o.l) return l < o.l;
		else return r < o.r;
	}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int vis[N][N];

PII qwq[N * N];
int h = 0, ta = 1;
int viss[N];
inline void bfs(int x, int y)
{
//	cout << y << "----------------------\n";
	h = 0, ta = 1;
	qwq[++h] = mk(x, y);
	while(ta - h + 1)
	{
		PII t = qwq[ta];
		if(ta >= h) ta--;
//		cout << t.x << " " << t.y << endl;
		if(t.x == n) viss[t.y] = 1;
		vis[t.x][t.y] = y;
		for(int i = 1;i <= 4;i++)
		{
			int x1 = t.x + dx[i], y1 = t.y + dy[i];
			if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1] == y) continue;
			qwq[++ta] = mk(x1, y1);
			if(x1 == n)
			{
				segment[y].l = (segment[y].l < y1 ? segment[y].l : y1);
				segment[y].r = (segment[y].r > y1 ? segment[y].r : y1);
			}
		}
	}
}
int check[N];
int main()
{
// 	freopen("in./in", "r", stdin);
// 	freopen("out.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			cin >> Map[i][j];
		}
	}
	for(int i = 1;i <= m;i++)
	{
		segment[i].l = 0x3f3f3f3f;
		segment[i].r = -0x3f3f3f3f;
		if(n == 1) segment[i].l = i, segment[i].r = i;
		bfs(1, i);
	}


	int cn = 0;
	for(int i = 1;i <= m;i++)
	{
		if(!viss[i])//就是这里
		{
			cn++;
		}
	}

	if(cn)
	{
		cout << 0 << "\n" << cn;
		exit(0);
	}

	sort(segment + 1, segment + 1 + m);

	int lst = 1;
	int cnt = 0;
	for(int i = 1;i <= m;i++)
	{
		if(segment[i].l == 0x3f3f3f3f) break;
//		cout << i << " " << segment[i].l << " " << segment[i].r << endl; 
		if(segment[i].l > lst)
		{
//			cout << "chosen:" << i - 1 << endl;
			lst = segment[i - 1].r + 1;
			cnt ++;
		}
	}
	if(lst != m + 1) cnt++;
	cout << 1 << "\n" << cnt;
	return 0;
}