火星探险问题

前置知识

最大费用最大流

建图

每个石头只能被获取一次，就可以考虑网络流的常规做法，把每个点拆成2个点（入点和出点）
（下面所说的连边都是双向边，网络流基础，不知道的同学建议先学习网络流）

考虑入点连向出点的边

如果这个点为障碍，那么入点不向出点连边，即这个点永远不会被经过
如果这个点不为障碍，那么入点向出点连容量为inf，代价为0的边
如果这个点为石头，那么入点向出点连容量为1，代价为1的边（容量为1保证了这个石头只被计算一次）

考虑出点连向入点的边

这种边即原图中点与点的边，从一个点的出点连向其南方和东方的点的入点即可

费用流

我们需要最多的石头，在建边时，我们将石头赋值到了边权，所以我们使用最大费用最大流

输出

跑完最大费用最大流模板后，考虑如何输出
对每个探测车进行dfs
首先要判断探测车走的方向是否正确（只能向南和东走）
其次查看这条边的反向边是否有流量，如果有，则探测车可以走这边，把这条反向边的流量-1

参考代码

#include<bits/stdc++.h>
using namespace std;
int k,n,m,S,T;
int get(int x,int y){
    return (x*m+y-1)*2;
}
const int N=100000,M=1000000,inf=101010;
struct oppo{
    int to,nex,s,w;
}rod[M];
int head[N],tot;
void add(int from,int to,int s,int w)
{
    rod[tot].nex=head[from];
    rod[tot].to=to;
    rod[tot].s=s;
    rod[tot].w=w;
    head[from]=tot++;
}
void link(int from,int to,int s,int w)
{
    add(from,to,s,w);
    add(to,from,0,-w);
}
int d[N],cur[N];
bool f[N];
bool spfa()
{
    queue<int> v;
    memset(f,0,sizeof(f)); 
    memset(d,-1,sizeof(d));
    d[S]=0,cur[S]=head[S];
    v.push(S);
    while(v.size()){
        int lxl=v.front();v.pop();
        f[lxl]=0;
        for(int i=head[lxl];~i;i=rod[i].nex){
            int to=rod[i].to;
            if(d[to]<d[lxl]+rod[i].w&&rod[i].s){
                d[to]=d[lxl]+rod[i].w;
                cur[to]=head[to];
                if(to==T) return 1;
                if(!f[to]){
                    v.push(to);
                    f[to]=1;
                }
            }
        }
    }
    return 0;
}
bool vis[N];
int ANS;
int find(int x,int low)
{
    if(x==T){
        ANS+=d[T]*low;
        return low;
    } 
    vis[x]=1;
    int all=0;
    for(int i=cur[x];~i;i=rod[i].nex)
    {
        cur[x]=i;
        int to=rod[i].to;
        if(!vis[to]&&d[to]==d[x]+rod[i].w&&rod[i].s){
            int t=find(to,min(rod[i].s,low-all));
            if(!t) d[to]=-1;
            rod[i].s-=t;
            rod[i^1].s+=t;
            all+=t;
        }
        if(all==low) break;
    }
    vis[x]=0;
    return all;
}
void dinic()
{
    while(spfa()) while(find(S,inf));
}
void dfs(int x,int k)
{
    if(x==T) return;
    for(int i=head[x];~i;i=rod[i].nex){
        int to=rod[i].to;
        if(to>x&&rod[i^1].s){
            if(x&1&&to!=T){
                if(to==x+1) printf("%d 1\n",k);
                else printf("%d 0\n",k);
            }
            dfs(rod[i].to,k);
            rod[i^1].s--;
            return;
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>k>>m>>n;
    S=0,T=get(n,m)+2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int t;
            scanf("%d",&t);
            if(t!=1) link(get(i,j),get(i,j)^1,inf,0);
            if(t==2) link(get(i,j),get(i,j)^1,1,1);
        }
    getchar();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(j!=m) link(get(i,j)^1,get(i,j+1),inf,0);
            if(i!=n) link(get(i,j)^1,get(i+1,j),inf,0);
        }
    link(S,get(1,1),k,0);
    link(get(n,m)^1,T,inf,0);
    dinic();
    for(int i=1;i<=k;i++)
        dfs(S,i);
    return 0;
}