社区讨论
求调! 第四个点错误
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 条回复,欢迎继续交流。
正在加载回复...