题目地址：http://hihocoder.com/problemset/problem/1114
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
“我们还是循序渐进，先来考虑这样一个简单化问题：”小Hi思索片刻，道：“在一个大小为2*N的广场，其中第一行里的某一些格子里可能会有至多一个地雷，而第二行的格子里全都为数字，表示第一行中距离与这个格子不超过2的格子里总共有多少个地雷，即第二行的第i个格子里的数字表示第一行的第i-1个, 第i个, 第i+1个，三个格子（如果i=1或者N则不一定有三个）里的地雷的总数。”
“而我们要做的是——找出哪些地方一定是雷，哪些地方一定不是雷。”小Ho道：“不然，我可就要光荣牺牲了。”
提示：寻找关键点——那些一旦决定之后就能让局面豁然开朗的地方。
输入
每个测试点（输入文件）存在多组测试数据。
每个测试点的第一行为一个整数Task，表示测试数据的组数。
在一组测试数据中：
第1行为1个整数N，表示迷宫的宽度。
第2行为N个整数A_1 … A_N，依次表示迷宫第二行的N个格子里标注的数字。
对于100%的数据，满足1<=N<=10^5, 0<=a_i<=3.<>
对于100%的数据，满足符合数据描述的地图一定存在。
输出
对于每组测试数据，输出2行，其中第一行先输出一定为地雷的格子的数量，然后按照从小到大的顺序输出所有一定为地雷的格子的位置，第二行先输出一定不为地雷的格子的数量，按照从小到大的顺序输出所有一定不为地雷的格子的位置。
样例输入
2
3
1 1 1
10
1 2 1 2 2 3 2 2 2 2
样例输出
1 2
2 1 3
7 1 3 5 6 7 9 10
3 2 4 8
Java 代码如下：
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);int t,n;t=in.nextInt();for(int i=0;i<t;i++){n=in.nextInt();int[] count=new int[n+2];for(int j=1;j<n+1;j++){count[j]=in.nextInt();}int num=0;int[][] map=new int[2][n+2];for(int l=0;l<=1;l++){ map[l][1]=l;int flag=0;for(int j=1;j<n;j++){ //1-n-1 //设值if(count[j]<map[l][j-1]+map[l][j]+map[l][j+1]){break;}if(count[j]>map[l][j-1]+map[l][j]+map[l][j+1]){map[l][j+1]=1;}}for(int j=1;j<n+1;j++){ //判断是否合法if(count[j]!=map[l][j-1]+map[l][j]+map[l][j+1]){flag=1;break;}}if(flag==0){ //标记哪个方案可行num+=l+1;}}int mine=0,nmine=0;switch (num) {case 3:int[] comm=new int[n+1];Arrays.fill(comm, -1);for(int j=1;j<n+1;j++){if(map[0][j]==map[1][j]){comm[j]=map[0][j];if(comm[j]==0){nmine+=1;}else{mine+=1;}}}System.out.print(mine); //雷for(int j=1;j<n+1;j++){if(comm[j]==1){System.out.print(" "+j);}}System.out.println();System.out.print(nmine); //非雷for(int j=1;j<n+1;j++){if(comm[j]==0){System.out.print(" "+j);}}System.out.println();break;default:for(int j=1;j<n+1;j++){mine+=map[num-1][j];}System.out.print(mine); //雷for(int j=1;j<n+1;j++){if(map[num-1][j]==1){System.out.print(" "+j);}}System.out.println();System.out.print(n-mine); //非雷for(int j=1;j<n+1;j++){if(map[num-1][j]==0){System.out.print(" "+j);}}System.out.println();break;}}}}
思路：先假设第一个位置不是雷，从左到右推一遍，再假设第一个位置是雷，推一遍。如果只有一种情况成立，就直接输出，如果两种都可能，就输出两次结果相同的。
先开始没有想到（也没有看清题目）存在两种都成立的可能，看到网上大神们的提示才意识到这个问题。