题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 550;
int n, m;
int g[N][N];
int l[N][N], r[N][N];
bool st[N][N];
int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
int f[N][N];
void dfs(int x, int y)
{
st[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (g[nx][ny] >= g[x][y]) continue;
if (!st[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()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j];
memset(l, 0x3f, sizeof l);
memset(r, -0x3f, sizeof r);
for (int i = 1; i <= m; i++)
l[n][i] = r[n][i] = i;
for(int i = 1;i <= m;i ++)
if (!st[1][i])
dfs(1, i);
int cnt = 0;
for (int i = 1; i <= m; i++)
cnt += !st[n][i];
if (cnt)
{
printf("0\n%d", cnt);
return 0;
}
cout<<"1\n";
memset(f,0x3f,sizeof(f));
f[0][0]=0;
int res=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int left=l[1][i],right=r[1][i];
for(int j=0;j<=m;j++) f[i][j]=f[i-1][j];
if(left==0x3f3f3f3f) continue;
for(int j=left;j<=right;j++)
{
f[i][j]=min(f[i][j],f[i-1][left-1]+1);
//cout<<f[i][j]<<" ";
}
res=min(res,f[i][m]);
//<<endl;
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla