思路：记忆化搜索，记录每一个点若装装置可以到的最后一排的位置，使用bitset(AC代码面向数据点编程)

#include <bits/stdc++.h>
using namespace std;
const int maxn=505;
int a[maxn][maxn];
int n,m;
int idx(int x,int y){
	return (x-1)*m+y;
}
int fst[maxn*maxn],nxt[maxn*maxn<<4],e[maxn*maxn<<4],cnt;
bitset<maxn> des[maxn*maxn],dp[maxn];
void add(int x,int y){
	nxt[++cnt]=fst[x];
	fst[x]=cnt;
	e[cnt]=y;
}
void check(int x,int y,int xx,int yy){
	if(xx<=0&&xx>m) return ;
	if(yy<=0&&yy>m) return ;
	if(a[xx][yy]>a[x][y]) add(idx(xx,yy),idx(x,y));
}
queue<int> q;
int vis[maxn*maxn];
void dfs(int x){
	for(int i=fst[x];i;i=nxt[i]){
		int to=e[i];
		if(!vis[to]) dfs(to);
		vis[to]=1;
		des[x]|=des[to];
	}
}
signed main() {
//	freopen("P1514_3.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			check(i,j,i-1,j);
			check(i,j,i,j-1);
			check(i,j,i,j+1);
			check(i,j,i+1,j);
			if(i==n){
				des[idx(i,j)][j]=1;
			}
		}
	}
	for(int i=1;i<=m;i++){
		dfs(i);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if((dp[i-1]|des[j]).count()>dp[i].count()){
				dp[i]=dp[i-1]|des[j];
			}
		}
	}
	if(dp[m].count()<m){
		printf("0\n%d",m-dp[m].count());
	}
	else{
		for(int i=1;i<=m;i++){
			if(dp[i].count()==m){
				printf("1\n%d",i);
				break;
			}
		}
	}
	return 0;
}