[NOIP2010 提高组] 引水入城

广搜+递推+最少线段覆盖

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500;
int n, m;
int a[MAXN + 5][MAXN + 5];
queue<pair<int, int>> q;
bool vis[MAXN + 5][MAXN + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};  
// 存所有点，为递推顺序做准备 
vector<pair<int,int>> points;  
bool cmp(pair<int,int> x, pair<int,int> y)
{
	return a[x.first][x.second] < a[y.first][y.second];
}
// a[i][j] 能走到  a[n][first ~ seoncd] 
pair<int,int> L[MAXN + 5][MAXN + 5];

vector<pair<int,int>> b; 
signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
			
	// 1. 第一行为起点的搜索，判断是否有解
	for (int j = 1; j <= m; j++)
	{
		vis[1][j] = true;
		q.push(make_pair(1, j));
	}
	while(!q.empty())
	{
		pair<int, int> now = q.front();
		q.pop();
		for (int i = 0; i <= 3; i++)
		{
			int nx = now.first + dx[i];
			int ny = now.second + dy[i];
			if (1 <= nx && nx <= n &&
			    1 <= ny && ny <= m &&
				!vis[nx][ny] &&
				a[nx][ny] < a[now.first][now.second])
			{
				vis[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}
	// 算算最后一行有几个位置不可以
	int cnt = 0;
	for (int j = 1; j <= m; j++)
		if (!vis[n][j]) 
			cnt++;
	if (cnt != 0)
	{
		cout << 0 << "\n";
		cout << cnt << "\n";
		return 0;
	}
	// 2. 构建每个第一行的点对应的区间
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			points.push_back(make_pair(i, j));
	sort(points.begin(), points.end(), cmp); 
	/*
	for(int i=0;i<points.size();i++)
		cout<<points[i].first<<" "<<points[i].second<<"\n";
	*/
	for(int i=0;i<points.size();i++)
	{
		int x = points[i].first;
		int y = points[i].second;
		L[x][y].first = m+1;
		L[x][y].second = 0;
		if(x==n)
			L[x][y] = make_pair(y,y);
		for(int j=0;j<=3;j++){
			int nx = points[i].first + dx[j];
			int ny = points[i].second + dy[j];
			if (1 <= nx && nx <= n &&
			    1 <= ny && ny <= m &&
				a[nx][ny] < a[x][y])
			{ 
				L[x][y].first = min(L[x][y].first, L[nx][ny].first);
				L[x][y].second = max(L[x][y].second, L[nx][ny].second);
			}
		}
	}
	for(int j=1;j<=m;j++)
	{
		//cout<<j<<":"<<L[1][j].first<<" "<<L[1][j].second<<"\n";
		if(L[1][j].first<=L[1][j].second)
			b.push_back(L[1][j]);
	}
	// 3. 最少区间覆盖问题 
	// b 数组里面的这些区间最少用几个能覆盖 1~m 
	sort(b.begin(), b.end());//其实不用排序
	int l = 1, r = 0; 
	int ans = 0;
	while (r < m) {
		for (int i = 0; i < b.size(); i++)
			if (b[i].first <= l && l <= b[i].second)
				r = max(r, b[i].second);
		l = r + 1;
		ans++;
	}
	cout << 1 << "\n";
	cout << ans << "\n";
	return 0;
}

深搜+记忆化搜索+最少线段覆盖

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int n, m;
int a[MAXN + 5][MAXN + 5];
bool vis[MAXN + 5][MAXN + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void dfs(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (1 <= xx && xx <= n &&
            1 <= yy && yy <= m &&
            a[xx][yy] < a[x][y] &&
            vis[xx][yy] == false)
        {
            vis[xx][yy] = true;
            dfs(xx, yy);
        }
    }
}
// 存第一行能访问到的所有区间
vector<pair<int, int>> b;
pair<int, int> book[MAXN + 5][MAXN + 5];
pair<int, int> dfsdfs(int x, int y)
{
    if (book[x][y].first != 0 || book[x][y].second != 0)
        return book[x][y];
    int l, r;
    l = m + 1, r = 0;
    if (x == n)
        l = r = y;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (1 <= xx && xx <= n &&
            1 <= yy && yy <= m &&
            a[xx][yy] < a[x][y])
        {
            pair<int, int> nxt = dfsdfs(xx, yy);
            l = min(l, nxt.first);
            r = max(r, nxt.second);
        }
    }
    return book[x][y] = make_pair(l, r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    // 1. 判断是否有解，从第一行开始搜看能否覆盖下面的所有位置
    for (int j = 1; j <= m; j++)
        if (vis[1][j] == false)
        {
            vis[1][j] = true;
            dfs(1, j);
        }
    int cnt = 0; // 有几个位置没有被染上
    for (int j = 1; j <= m; j++)
        if (vis[n][j] == false)
            cnt++;
    if (cnt > 0)
    {
        cout << "0\n";
        cout << cnt << "\n";
        return 0;
    }
    // 2. 算出来第一行每个位置能覆盖哪个区间
    for (int j = 1; j <= m; j++)
        b.push_back(dfsdfs(1, j));
    // 3. 最少区间覆盖
    int ans = 0;
    int last = 0; // 上一个覆盖到的位置，接下来要覆盖 last+1
    while (last != m)
    {
        int now = last + 1; // 当前要覆盖 last+1
        for (int i = 0; i < b.size(); i++)
        {
            if (b[i].first <= now && now <= b[i].second)
                last = max(last, b[i].second);
        }
        ans++;
    }
    cout << 1 << "\n";
    cout << ans;
    return 0;
}