我好蒟蒻呀
连区间覆盖这个贪心都不会
我的写法好水呀
启示:要转化问题
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
queue<int> q;
bool visit[510][510];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,-1,1};
int tot;
int n,m;
int map[510][510];
bool vis[510][510];
bool used[510];
struct LINE
{
int l;
int r;
};
LINE line[510];
int l;
bool check(int x,int y)
{
if(x<=0||y<=0||x>n||y>m||vis[x][y])
return false;
return true;
}
void BFS()
{
int x,y;
while(!q.empty())
{
x=q.front();q.pop();
y=q.front();q.pop();
if(x==n)
tot+=1;
for(int i=0;i<=3;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(check(nx,ny)&&map[x][y]>map[nx][ny])
{
q.push(nx);q.push(ny);
vis[nx][ny]=true;
}
}
}
}
void bfs(int begin)
{
l+=1;
q.push(1);
q.push(begin);
vis[1][begin]=true;
int x,y;
line[l].l=510;
used[begin]=true;
while(!q.empty())
{
x=q.front();
q.pop();
y=q.front();
q.pop();
if(x==n)
{
line[l].l=min(line[l].l,y);
line[l].r=max(line[l].r,y);
}
for(int i=0;i<=3;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(check(nx,ny)&&map[x][y]>map[nx][ny])
{
q.push(nx);
q.push(ny);
vis[nx][ny]=true;
if(nx==1)
used[ny]=true;
}
}
}
}
struct re
{
int h;
int y;
};
re rep[510];
bool compare1(const re &a,const re &b)
{
return a.h>b.h;
}
bool compare2(const LINE &a,const LINE &b)
{
if(a.l!=b.l)
return a.l<b.l;
return a.r<b.r;
}
int main()
{
//freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=m;i++)
{
q.push(1);
q.push(i);
vis[1][i]=true;
}
BFS();
if(tot==m)
{
/* for(int i=1;i<=m;i++)
{
rep[i].h=map[1][i];
rep[i].y=i;
}
sort(rep+1,rep+1+m,compare1);*/
for(int i=1;i<=m;i++)
{
memset(vis,0,sizeof(vis));
bfs(i);
//printf("1 %d
%d %d
",i,line[l].l,line[l].r);
}
sort(line+1,line+1+l,compare2);
tot=0;
int now=0,nxt=1;
/*for(int i=1;i<=l;i++)
{
tot+=1;
now=max(nxt,line[i].l);
for(;line[i].l<=now&&nxt!=m&&i<=l;i++)
nxt=max(nxt,line[i].r);
i-=1;
}*/
int last=1;
int i=1;
while(last<=m)/*坑爹的模板*/
{
int t=0;
while(line[i].l<=last) t=max(t,line[i++].r);
last=t+1;
tot+=1;
}
printf("1
%d",tot);
}
else
{
printf("0
%d",m-tot);
return 0;
}
}