/*---------------------------------------------------------------------------
File name: C76-21.cpp
Author: HJin (email: fish_sea_bird[at]yahoo.com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

经典 76 道编程题 之 21:

21. 请设计一个程序，由计算机把1－8的八个自然数填入图中，使得横、
竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
为禁止的情形).
┌─┐ ┌─┐ ┌─┐
│ │ │4 │ │8 │
┌─┼─┼─┐ └─┼─┐ ┌─┼─┘
│ │ │ │ │5 │ │7 │
├─┼─┼─┤ └─┘ └─┘
│ │ │ │ ┌─┐
└─┼─┼─┘ │6 │ ┌─┬─┐
│ │ ├─┤ │1 │2 │
└─┘ │7 │ └─┴─┘
└─┘

Analysis:
---------------------------------------------------------------------------

Check all neighbors of (i, j) to see if a matrix is valid.

Sample output:
---------------------------------------------------------------------------
(Totally there are four arrangements satisfying the requirements.)

#1
--------------------------------
2
5 8 6
3 1 4
7

#2
--------------------------------
2
6 8 5
4 1 3
7

#3
--------------------------------
7
3 1 4
5 8 6
2

#4
--------------------------------
7
4 1 3
6 8 5
2
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
http://bbs.bc-cn.net/viewthread.php?tid=147967

*/

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

/**
absolute value of a.
*/
inline int abs(int a);

/**
Is it a valid matrix?
*/
bool isValid(int a[][3]);

/**
Do all the neighbors agree with you?
*/
bool checkNeighbors(int a[][3], int i, int j);

/**
copy b[] into a[][].
*/
void copy(int a[][3], int* b);

/**
output results.
*/
void print(int a[][3], int counter, std::ostream& os= cout);

int main(int argc, char** argv)
{
int a[4][3];
int b[8];
int i;
int counter = 0;
ofstream ofs("C76-21-Ans.txt");
if(!ofs)
{
cout<<"cannot open file C76-21-Ans.txt.\n";
exit(0);
}

a[0][0] = -1;
a[0][2] = -1;
a[3][0] = -1;
a[3][2] = -1;

for(i=0; i<8; ++i)
b[i] = i+1;
copy(a, b);
if(isValid(a))
{
++counter;
print(a, counter);
}

while( next_permutation(b, b+8) )
{
copy(a, b);
if(isValid(a))
{
++counter;
print(a, counter);
print(a, counter, ofs);
}

}

ofs.close();

return 0;
}

bool isValid(int a[][3])
{
int i;
int j;

for(i=0; i<4; ++i)
{
for(j=0; j<3; ++j)
{
if( a[i][j] > 0 && (!checkNeighbors(a, i, j)) )
{
return false;
}
}

}

return true;
}

bool checkNeighbors(int a[][3], int i, int j)
{
/**
i \in [0, 3];
j \in [0, 2];

(i,j) can have 3, 5, or 8 neighbors.
*/

if(
( i>=1 && abs(a[i][j] - a[i-1][j]) == 1 ) || /** check (i-1, j) */
( i<=2 && abs(a[i][j] - a[i+1][j]) == 1 ) || /** check (i+1, j) */
( j>=1 && abs(a[i][j] - a[i][j-1]) == 1 ) || /** check (i, j-1) */
( j<=1 && abs(a[i][j] - a[i][j+1]) == 1 ) || /** check (i, j+1) */
( (i>=1 && j>=1) && abs(a[i][j] - a[i-1][j-1]) == 1 ) || /** check (i-1, j-1) */
( (i>=1 && j<=1) && abs(a[i][j] - a[i-1][j+1]) == 1 ) || /** check (i-1, j+1) */
( (i<=2 && j>=1) && abs(a[i][j] - a[i+1][j-1]) == 1 ) || /** check (i+1, j-1) */
( (i<=2 && j<=1) && abs(a[i][j] - a[i+1][j+1]) == 1 ) /** check (i+1, j+1) */
)
{
return false;
}

return true;
}

int abs(int a)
{
return a>=0 ? a: -a;
}

void copy(int a[][3], int* b)
{
a[0][1] = b[0];
a[1][0] = b[1];
a[1][1] = b[2];
a[1][2] = b[3];
a[2][0] = b[4];
a[2][1] = b[5];
a[2][2] = b[6];
a[3][1] = b[7];
}

void print(int a[][3], int counter, std::ostream& os)
{
int i;
int j;

os<<"\n#"<<counter<<endl;
os<<"--------------------------------\n";
for(i=0; i<4; ++i)
{
for(j=0; j<3; ++j)
{
if(a[i][j]>0)
{
os<<a[i][j]<<" ";
}
else
{
os<<" ";
}
}
os<<endl;
}
}

我没时间啊... 你帮我写一个? 谢拉...
要用空格, 不要用制表符啊...

ps... 今年是猪年没错.. .. 和我有啥关系?..

31题：
解答说明：
甲只要保证第一次取完后留给乙的棋子数是2的n次方，且大于所取走的棋子数就必胜
因此，如果开始的棋子数是2的n次方，则甲无必胜方法
下面的程序演示了甲的策略，（程序包含了出错处理，所以比较长）

程序代码：

#include <iostream>
using namespace std;

#define MAX 100000
int num(int n,int k=0);
int main()
{
 int n,k,m;
 cout<<\"请输入不大于\"<<MAX<<\"的正整数，输入0退出\"<<endl;
 while(cin>>n&&(n>MAX||n<0))
  cout<<\"请重新输入\"<<endl;
 if(n==0)
  goto END;
 m=num(n);
 if(m<0)
  goto END;
 n-=m;
 while(n!=0)
 {
  cout<<\"我取走\"<<m<<\"\t剩余：\"<<n<<endl<<\"请问你取走多少个？\"<<endl;
  while(cin>>k&&(k>m||k<0||k>n))
   cout<<\"请重新输入\"<<endl;
  if(k==0)
   goto END;
  n-=k;
  cout<<\"你取走\"<<k<<\"\t剩余：\"<<n<<endl;
  if(n==0)
  {
   cout<<\"你胜利了！\"<<endl;
   goto END;
  }
  m=num(n,k);
  if(m<0)
   goto END;
  n-=m;
 }
 cout<<\"我取走\"<<m<<\"\t剩余：\"<<n<<endl;
 cout<<\"你输了\"<<endl;
END:system(\"pause\");
 return 0;
}
int num(int n,int k)
{
 if(n<=k)
  return n;
 int i,t=1;
 while(t<=n)
 {
  t*=2;
 }
 t/=2;
 if(t==n)
 {
  if(k==0)
   cout<<\"非必胜\"<<endl;
  t=n/2-2;
 }
 else if(k==0)
  cout<<\"必胜\"<<endl;
 t=n-t;
 if(t>k&&k!=0)
 {
  t=1;
  while(t<=k&&n%t==0)
   t*=2;
  t/=2;
 }
 if(t<1||(k!=0&&t>k)||t>n)
 {
  cout<<\"Error:\"<<endl<<n<<\"\t\"<<k<<\"\t\"<<t<<endl;
  return -1;
 }
 return t;
}