社区讨论

求调! 第四个点错误

P1514[NOIP 2010 提高组] 引水入城参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhizbfsz
此快照首次捕获于
2025/11/03 18:10
4 个月前
此快照最后确认于
2025/11/03 18:10
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

const int N = 510; 
int g[N][N]; 
int n, m;  
bool st[N]; 
bool vis[N][N]; 

struct Range{
    int l, r; 
    bool operator<(const Range & R)const{ 
        return l < R.l; 
    }
}range[N]; 

int cnt = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; 


void dfs(int x, int y, int &L, int &R){
    vis[x][y] = true;
  
    if(x == n){
        L = min(L, y); 
        R = max(R, y); 
    }
        
    for(int i = 0; i < 4; i++){ 
        int a = x + dx[i], b = y + dy[i]; 
        if(a >= 1 && a <= n && b >= 1 && b <= m){ 
            if(!vis[a][b] && (g[x][y] > g[a][b])){
                dfs(a ,b ,L,R); 
            }             
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);    
    cin >> n >> m; 
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++){ 
            cin >> g[i][j]; 
        }
    }
    
    // 按列顺序搜索,但避免重复搜索相同路径
    for(int i = 1; i <= m; i++){        
        memset(vis, false, sizeof vis);
        int L = 1e9, R = -1; 
        dfs(1, i, L, R);
        if(L == 1e9) continue; // 没有到达底部
        range[cnt++] = {L, R};
        // 标记覆盖的列
        for(int j = L; j <= R; j++) st[j] = true;
    }
    
    int num = 0;
    for(int i = 1; i <= m; i++) if(!st[i]) num++;
    
    if(num == 0){
        sort(range, range + cnt); 
        int res = 0;
        int S = 1; 
        bool flag = false;
        for(int i = 0 ;i < cnt ; i++) {
            int j = i , r = -1e9; 
            while(j < cnt && range[j].l <= S){ 
                r = max(r,range[j].r); 
                j++; 
            } 
            if(r < S){
                res = -1; 
                break; 
            }
            res++; 
            if(r == m){
                flag = true; 
                break; 
            }
            //r已经被覆盖了,所以我们要去覆盖下一个
            S = r + 1; 
            i = j - 1; 
        }
       
        if(res != -1)cout << 1 << endl << res << endl;
        else cout << 0 << endl << num << endl; 
    } else {
        cout << 0 << endl << num << endl;
    }
}

回复

0 条回复,欢迎继续交流。

正在加载回复...