搜索+贪心。
参考博客:http://blog.sina.com.cn/s/blog_8442ec3b0100xib1.html
主要是要看出来,如果有解的话,每个沿湖城市能够流到的范围是连续的区间...然后1遍dfs判断有无解,2遍确定区间,最后排序贪心。
直觉上来说,如果流到的区域中间是断的,那么中间的地势一定比两边高,从其他地方也流不到。
(理论上是应该bfs的= =)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
using namespace std;
#define tr(x) printf(#x),putchar('\n')
typedef pair<int, int> P;
const int MAXN = 600, dir[] = {0, 0, 1, -1}, INF = 0x3f3f3f3f;
int H[MAXN][MAXN], vis[MAXN][MAXN], cnt, M, N;
P r[MAXN]; //第一行每个城市可以流到的范围
void dfs(int x, int y){
vis[x][y] = 1;
if(x == N - 1){
++cnt;
}
for(int i = 0; i < 4; ++i){
int dx = x + dir[i], dy = y + dir[3-i];
if(0 <= dx && dx < N && 0 <= dy && dy < M && !vis[dx][dy] && H[dx][dy] < H[x][y]){
dfs(dx, dy);
}
}
}
void dfsL(int s, int x, int y){
vis[x][y] = 1;
if(x == 0){
r[y].first = s;
}
for(int i = 0; i < 4; ++i){
int dx = x + dir[i], dy = y + dir[3-i];
if(0 <= dx && dx < N && 0 <= dy && dy < M && !vis[dx][dy] && H[dx][dy] > H[x][y]){
dfsL(s, dx, dy);
}
}
}
void dfsR(int s, int x, int y){
vis[x][y] = 1;
if(x == 0){
r[y].second = s;
}
for(int i = 0; i < 4; ++i){
int dx = x + dir[i], dy = y + dir[3-i];
if(0 <= dx && dx < N && 0 <= dy && dy < M && !vis[dx][dy] && H[dx][dy] > H[x][y]){
dfsR(s, dx, dy);
}
}
}
int main(){
freopen("in.txt", "r", stdin);
scanf("%d%d", &N, &M);
for(int i = 0; i < N; ++i){
for(int j = 0; j < M; ++j){
scanf("%d", &H[i][j]);
}
}
for(int i = 0; i < M; ++i){
if(!vis[0][i]) dfs(0, i);
}
if(cnt < M){
printf("0\n%d\n", M - cnt);
return 0;
}
//======================================
for(int i = 0; i < M; ++i){
r[i].first = INF;
}
memset(vis, 0, sizeof(vis));
for(int i = 0; i < M; ++i){
if(!vis[N - 1][i]){
dfsL(i, N-1, i);
}
}
memset(vis, 0, sizeof(vis));
for(int i = M-1; i >= 0; --i){
if(!vis[N - 1][i]){
dfsR(i, N-1, i);
}
}
sort(r, r + M);
int ans = 0, nowr = -1, maxr, i = 0;
while(i < M && nowr < M - 1){
maxr = -1;
while(i < M && r[i].first <= nowr + 1){
maxr = max(maxr, r[i].second);
++i;
}
nowr = maxr;
++ans;
}
printf("1\n%d\n", ans);
return 0;
}