hihoCoder#1114 小Hi小Ho的惊天大作战：扫雷・一 - 李舜阳 - 博客园

http://hihocoder.com/problemset/problem/1114

故事背景：密室、监视器与充满危机的广场

“我们还是循序渐进，先来考虑这样一个简单化问题：”小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 

http://beeder.github.io/2015/05/29/hihoCoder-Problem-1114/  每个点只有0个或1个雷，只要确定了第一个点的雷数，后面的雷数就依次确定了。所以最多有两种情况：第一个点有0个或1个雷。

  假设第一个点有0个或1个雷，通过计算可得所有点的雷数，如果雷数不符合题意，则假设不合理。然后再确定所有合法方案中一定有雷或无雷的点。

const int kMax = 100005;

int n;

int mine10[kMax];

int mine11[kMax];

int mine2[kMax];

int yes_id[kMax];

int no_id[kMax];



bool Sub(int x,int *mine1x)

{

 mine1x[0] = 0;

 mine1x[1] = x;

 for (int i = 2; i <= n; i++)

 {

  mine1x[i] = mine2[i - 1] - mine1x[i - 1] - mine1x[i - 2];

  if (mine1x[i] != 0 && mine1x[i] != 1)

   return false;

 }

 if (mine1x[n] + mine1x[n - 1] != mine2[n])

  return false;

 return true;

}

void Solve()

{

 bool ans0=Sub(0,mine10);

 bool ans1=Sub(1,mine11);

 int yes_num = 0, no_num = 0;

 if (ans0&&!ans1)

 {

  for (int i = 1; i <= n; i++)

  {

   if (mine10[i] == 1)

    yes_id[yes_num++] = i;

   else

    no_id[no_num++] = i;

  }

 }

 else if (!ans0&&ans1)

 {

  for (int i = 1; i <= n; i++)

  {

   if (mine11[i] == 1)

    yes_id[yes_num++] = i;

   else

    no_id[no_num++] = i;

  }

 }

 else if (ans0&&ans1)

 {

  for (int i = 1; i <= n; i++)

  {

   if (mine10[i] == mine11[i])

   {

    if (mine10[i] == 1)

     yes_id[yes_num++] = i;

    else

     no_id[no_num++] = i;

   }

  }

 }

 

 printf("%d ", yes_num);

 for (int i = 0; i < yes_num; i++)

  printf("%d ", yes_id[i]);

 printf("\n");

 

 printf("%d ", no_num);

 for (int i = 0; i < no_num; i++)

  printf("%d ", no_id[i]);

 printf("\n");

 

}

int main()

{

 int t;

 scanf("%d", &t);

 while (t--)

 {

  scanf("%d", &n);

  for (int i = 1; i <= n; i++)

   scanf("%d", &mine2[i]);

  Solve();

 }

 return 0;

}

hihoCoder#1114 小Hi小Ho的惊天大作战：扫雷・一 - 李舜阳 - 博客园
回溯+搜索
枚举每个位置上能否放地雷，当第i个位置枚举完成后，第i-1个位置的情况就确定了，此时，检查第i-1个位置是否满足要求，即左右间隔为1的范围内地雷数是否等于申明数字，如果满足条件，那么继续搜索下去，如果不满足条件，抛弃这个搜索分支。
搜索完成后，将所有可行解按位置"与"一下 ，找到那些一定为地雷或一定为空的格子。

 6 void merge(int *t, int *r, int n) {
 7   for (int i = 0; i < n; i++) {
 8     if (t[i] == -1 || t[i] == r[i])
 9       t[i] = r[i];
10     else
11       t[i] = -2;
12   }
13 }
14 
15 void find(int *a, int *r, int *t, int p, int n) {
16   if (p >= n) {
17     if ((n == 1 && a[p - 1] == r[p - 1])
18         || ((n > 1) && a[p - 1] == r[p - 1] + r[p - 2]))
19       merge(t, r, n);
20   }
21   else if (p == 0) {
22     for (int i = 0; i < 2; i++) {
23       r[p] = i;
24       find(a, r, t, p + 1, n);
25     }
26   }
27   else if (p == 1) {
28     for (int i = 0; i < 2; i++) {
29       r[p] = i;
30       if (a[p - 1] == r[p - 1] + r[p])
31         find(a, r, t, p + 1, n);
32     }
33   }
34   else {
35     for (int i = 0; i < 2; i++) {
36       r[p] = i;
37       if (a[p - 1] == r[p] + r[p - 1] + r[p - 2])
38         find(a, r, t, p + 1, n);
39     }
40   }
41 }
42 
43 int main() {
44   int n;
45 
46   cin >> n;
47   while (n--) {
48     int N;
49     cin >> N;
50     int *a = new int[N];
51     int *r = new int[N];
52     int *t = new int[N];
53 
54     for (int i = 0; i < N; i++)
55       cin >> a[i];
56     memset(r, 0, N * sizeof(int));
57     memset(t, -1, N * sizeof(int));
58 
59     find(a, r, t, 0, N);
60 
61     int mine = 0;
62     int not_mine = 0;
63 
64     for (int i = 0; i < N; i++) {
65       mine += (t[i] == 1 ? 1 : 0);
66       not_mine += (t[i] == 0 ? 1 : 0);
67     }
68 
69     cout << mine;
70     for (int i = 0; i < N; i++)
71       if (t[i] == 1)
72         cout << " " << i + 1;
73     cout << endl;
74 
75     cout << not_mine;
76     for (int i = 0; i < N; i++)
77       if (t[i] == 0)
78         cout << " " << i + 1;
79     cout << endl;
80 
81     delete t;
82     delete r;
83     delete a;
84   }
85 
86   return 0;
87 }

http://www.aiuxian.com/article/p-2162945.html
int a[N],vis[N],ans[N],n,yes;  //vis是标记有无雷
int YES[N],NO[N];

bool judge(int pos)
{
if(pos==1)
{
if(n==1)
return vis[pos]==a[pos];
return a[pos]>=vis[pos];
}

if(pos==2)
{
int temp=vis[1]+vis[2];
if(n==2)
return a[1]==temp&&a[2]==temp;
return a[1]==temp;
}

int temp=vis[pos]+vis[pos-1]+vis[pos-2];

if(pos==n)
 return a[pos-1]==temp&&a[pos]==vis[pos]+vis[pos-1];

return a[pos-1]==temp;
}

void dfs(int pos)
{
int i,j;

    if(pos==n+1)
{
if(!yes)
{
yes=1;
for(i=1;i<=n;i++)   //第一次成功时复制到ans
ans[i]=vis[i];

return ;
}

for(i=1;i<=n;i++)
if(ans[i]!=vis[i])   //以后成功的情况看看有雷的地方是不是一定有雷
 ans[i]=-1;         //如果这种情况有雷,那种情况无雷这个点无法确定
return ;
}

vis[pos]=1;
if(judge(pos))
dfs(pos+1);

vis[pos]=0;
if(judge(pos))
dfs(pos+1);
}

void print()
{
int i,j,x,y;
x=0,y=0;

for(i=1;i<=n;i++)
{
if(ans[i]==1) YES[x++]=i;
if(ans[i]==0) NO[y++]=i;
}

printf("%d",x);
for(i=0;i<x;i++)
printf(" %d",YES[i]);
printf("\n");

printf("%d",y);
for(i=0;i<y;i++)
printf(" %d",NO[i]);
printf("\n");
}


int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
yes=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);

dfs(1);
print();
}
return 0;


}
http://m.blog.csdn.net/blog/piaocoder/47262185
Read full article from hihoCoder#1114 小Hi小Ho的惊天大作战：扫雷・一 - 李舜阳 - 博客园