C++14(g++5.4) 解法, 执行用时: 49ms, 内存消耗: 14436K, 提交时间: 2019-07-18 16:30:40
#include<bits/stdc++.h>
using namespace std;
#define nx x + dx[i]
#define ny y + dy[i]
const int dx[] = {1 , 0 , -1 , 0};
const int dy[] = {0 , 1 , 0 ,-1};
int n , m;
int s[1002][1002];
bool v[1020][1020];
int l[1002][1002] ;
int r[1020][1020];
bool in(int x ,int y){
return 1 <= x && x <=n &&1 <= y && y <= m;
}
void dfs(int x ,int y){
v[x][y] = 1;
for(int i = 0; i < 4 ;i++){
if (!in(nx , ny)) continue;
if(s[nx][ny] < s[x][y]) {
if(!v[nx][ny]){
dfs(nx,ny);
}
l[x][y] = min(l[x][y] , l[nx][ny]);
r[x][y] = max(r[x][y] , r[nx][ny]);
}
}
}
int cnt;
int main() {
memset(l , 0x3f , sizeof(l));
scanf("%d%d",&n , &m);
for(int i = 1; i <= m ; i++){
l[n][i] = r[n][i] = i;
}
for(int i = 1; i <= n ;i++){
for(int j = 1; j <= m; j++){
scanf("%d" ,&s[i][j]);
}
}
for(int i = 1; i <= m ; i++){
if(!v[1][i]){
dfs(1 , i);
}
}
bool flag = 0;
for(int i = 1; i <= m ; i++){
if(!v[n][i]){
cnt++;
flag = 1;
}
}
if(flag == 1){
puts("0");
cout << cnt << endl;
return 0;
}
int left = 1;
while(left <= m){
int maxx = 0;
for(int i = 1; i <= m;i++){
if(left >= l[1][i]){
maxx = max(maxx ,r[1][i]);
}
}
cnt++;
left = maxx + 1;
}
cout << 1 << endl;
cout << cnt << endl;
}
Pascal(fpc 3.0.2) 解法, 执行用时: 626ms, 内存消耗: 2124K, 提交时间: 2019-10-12 18:34:34
var
a: array [1..500, 1..500] of longint;
b: array [1..500, 1..500] of boolean;
l, r: array [1..500] of longint;
vis: array [1..500] of boolean;
n, m, i, j, s, h, t: longint;
procedure dfs(x, y, k: longint);
begin
if b[x, y] then
exit;
b[x, y] := true;
if x = n then
begin
if not vis[y] then
begin
dec(s);
vis[y] := true;
end;
if y < l[k] then l[k] := y;
if y > r[k] then r[k] := y;
end;
if (x > 1) and (a[x - 1, y] < a[x, y]) then dfs(x - 1, y, k);
if (x < n) and (a[x + 1, y] < a[x, y]) then dfs(x + 1, y, k);
if (y > 1) and (a[x, y - 1] < a[x, y]) then dfs(x, y - 1, k);
if (y < m) and (a[x, y + 1] < a[x, y]) then dfs(x, y + 1, k);
end;
begin
read(n, m);
for i := 1 to n do
for j := 1 to m do
read(a[i, j]);
s := m;
for i := 1 to m do
begin
l[i] := maxlongint;
r[i] := 0;
fillchar(b, sizeof(b), false);
dfs(1, i, i);
end;
if s > 0 then
begin
writeln(0);
writeln(s);
halt;
end
else
writeln(1);
s := 0;
h := 1;
while h <= m do
begin
inc(s);
t := 0;
for i := 1 to m do
if (l[i] <= h) and (r[i] > t) then
t := r[i];
h := t + 1;
end;
writeln(s);
end.
C++(clang++ 11.0.1) 解法, 执行用时: 44ms, 内存消耗: 7636K, 提交时间: 2022-11-27 20:56:04
#include<bits/stdc++.h>
#define N 510
#define M 0x7f
using namespace std;
bool t[N][N];
int n,m,k,le,ma,a[N][N],l[N][N],r[N][N],dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};
bool Check(int x,int y){if(x<1||x>n||y<1||y>m)return false; return true;}
void Dfs(int x,int y){
int nx,ny;t[x][y]=1;
for (int i=0;i<4;i++){
nx=x+dx[i];ny=y+dy[i];
if (!Check(nx,ny)||a[nx][ny]>=a[x][y]) continue;
if (!t[nx][ny]) Dfs(nx,ny);
l[x][y]=min(l[x][y],l[nx][ny]);
r[x][y]=max(r[x][y],r[nx][ny]);
}
}
int main(){
scanf("%d%d",&n,&m);k=ma=0;le=1;
memset(l,M,sizeof(l));memset(r,0,sizeof(r));memset(t,0,sizeof(t));
for(int i=1;i<=m;i++)l[n][i]=r[n][i]=i;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=m;i++)if(!t[1][i])Dfs(1,i);
for(int i=1;i<=m;i++)if(!t[n][i])k++;
if(k>0){printf("0\n%d\n",k);return 0;}
while(le<=m){
ma=0;
for(int i=1;i<=m;i++)if(l[1][i]<=le)ma=max(ma,r[1][i]);
k++;le=ma+1;
}printf("1\n%d\n",k);
}
