解题思路
很简单的贪心。
观察发现以下性质：
- 当 \(a_i=2\) 时，这一行一定只有两个目标，且第二个目标一定位于一个 \(a_j=1\) 的格子内；
- 当 \(a_i=3\)，那么当前列右边某一列发生转向的地方，\(a_j\not=0\)；
那么这道题就基本已经做出来了。因为 \(a_i=3\) 的格子转向格可以在任意非 \(0\) 列，而 \(a_i=2\) 的转向格一定在 \(a_j=1\) 列，那么我们考虑优先满足 \(a_i=2\) 的列的需求。显然，不管怎么填，占用的行数是固定的，那么我们考虑第 \(i\) 列填在第 \(i\) 行，这样可以有效避免一些重复。接下来我们填 \(a_i=3\) 的格子，贪心的从左往右找到第一个可以有转向格的列，然后直接填就可以了。最后把 \(a_i=1\) 的补上就结束了。
注意，我们填的时候不需要考虑有没有填过，直接无脑填就可以了，最后再去重。
综上，本题步骤如下：
- 从左往右找到所有 \(a_i=1\) 的列，并按顺序放入一个队列中；
- 从左往右枚举 \(a_i=2\) 的列，并不断弹出队首直到队首列在当前列右侧，然后在队首列填入一个目标，并标记为已填；
- 清空队列，从左往右枚举所有非 \(0\) 列，并放入队列中；
- 从左往右枚举 \(a_i=3\) 的列，找到第一个在当前列右侧的列，然后填入两个目标；
- 枚举剩余的没有被填过的 \(a_i=1\) 的列，向其中填入一个目标；
- 排序去重输出答案。
注意事项
- 在维护可填列的时候一定要使用队列来维护，贪心地从左往右填；
- 注意纵坐标是从上往下递增的，而不是从下往上。
AC 代码
应该是比较短的代码了吧……
#include<bits/stdc++.h>
#define N 100005
#define p push_back
#define C continue
#define re register
#define pii std::pair<int,int>
std::vector<pii> A;
int n,a[N],vis[N];
signed main(){scanf("%d",&n);
for(re int i=1;i<=n;++i)
scanf("%d",&a[i]);
std::queue<int> q;
for(re int i=1;i<=n;++i)
if(a[i]==1) q.push(i);
for(re int i=1;i<=n;++i){
if(a[i]!=2) C;
while(q.size()&&q.front()<i) q.pop();
if(q.empty()){puts("-1");return 0;}
A.p({i,i});
A.p({i,q.front()});
vis[q.front()]=1;q.pop();
}while(q.size()) q.pop();
for(re int i=1;i<=n;++i){
if(a[i]!=0&&!vis[i]) q.push(i);
}for(re int i=1;i<=n;++i){
if(a[i]!=3) C;
while(q.size()&&q.front()<=i) q.pop();
if(q.empty()){puts("-1");return 0;}
A.p({i,i});A.p({i,q.front()});
A.p({q.front(),q.front()});
vis[q.front()]=1;q.pop();
}for(re int i=1;i<=n;++i){
if(a[i]!=1) C;
if(vis[i]) C;A.p({i,i});
}std::sort(A.begin(),A.end());
int res=std::unique(A.begin(),A.end())-A.begin();
printf("%d\n",res);
for(re int i=0;i<res;++i){
printf("%d ",A[i].first);
printf("%d\n",A[i].second);
}
}