主题：第32次比赛的第二题
fenix124 [专家分：70] 发布于 2006-06-21 17:22:00
刚来不久，又是第一次出题，问题在所难免。
如果题目描述有问题或者以前已经有类似题目了，麻烦发新贴说明。
以下是题目，比赛时间到星期六中午12点.good luck
点灯游戏
一些手机上的游戏。开始时有n*n个灯，排成n行n列，每个灯都是熄灭的状态。而每次对一个灯进行操作，可以改变其本身和周围的灯的状态，熄的灯变亮，亮的灯变熄灭。这儿周围的意思就是如果灯的位置是(x,y)，那么能影响的灯就是(x,y),(x-1,y),(x,y+1),(x+1,y),(x,y-1),当然如果相应地方有灯。
显然对一个灯操作偶数次相当于没有操作，而操作了奇数次相当于只操作了一次。
现在给定一个n( 1<= n <= 20)，输出一个n*n的只包含0和1的方阵(0代表没有操作，1代表操作了一次)，进行这样的操作后能把所有的灯点亮。如果没有解则输出"NO SOLUTION".多个解则只输出一个即可
函数接口
void solve(int n);
一些例子
n = 1时
输出
1
n = 2时
输出
1 1
1 1
n = 3时，
输出
1 0 1
0 1 0
1 0 1
到时候测试如果即使n = 20的速度都特别快，那么将多次测试，所以不建议把每个n*n的存起来。
回复列表 （共11个回复）
沙发
fenix124 [专家分：70] 发布于 2006-06-21 17:23:00
test
板凳
iAkiak [专家分：8460] 发布于 2006-06-21 23:37:00
#include <cstdio>
typedef unsigned long ul;
void solve(int n)
{
const ul mask = (1<<n) - 1;
ul clicks[20];
int i, j;
if (n == 1)
{
printf("1\n");
return;
}
for (ul click = 0; click <= mask; click++)
{
ul a = 0, b = 0, c = click;
i = 0;
do
{
clicks[i] = c;
b ^= c;
b ^= (c << 1) & mask;
b ^= (c >> 1) & mask;
a = b;
b = c;
c = (a ^ mask) & mask;
} while(++i < n - 1);
clicks[i] = c;
b ^= c;
b ^= (c << 1) & mask;
b ^= (c >> 1) & mask;
if (b == mask)
{
for (i = 0; i < n; i++)
{
for (j = n - 1; j > 0; j--)
printf("%d ", (clicks[i]>>j)&1);
printf("%d\n", clicks[i]&1);
}
return;
}
}
printf("NO SOLUTION\n");
}
int main()
{
int n;
while(scanf("%d", &n)==1)
{
solve(n);
}
return 0;
}
3 楼
boxertony [专家分：23030] 发布于 2006-06-22 16:05:00
// VC6下调试通过
#include <stdio.h>
#define MAXSIZE 32
inline int test(int a[][MAXSIZE], int i, int j)
{
return a[i][j]^a[i-1][j]^a[i][j-1]^a[i][j+1];
}
bool solve(int n)
{
static int a[MAXSIZE][MAXSIZE] = {{0}, {0, 1}};
static int count = 1;
int i, j;
if(count == n)
{
// 通过测试第1～n-1行，直接放置第2~n行
for(i=1; i<n; ++i)
for(j=1; j<=n; ++j)
a[i+1][j] ^= !test(a, i, j);
// 测试最后一行（第n-1行），全部通过说明得到解，否则无解
for(j=1; j<=n; ++j)
if(test(a, n, j) == 0)
break;
if(j <= n)
{// 没有找到解，则复原
memset(&a[2][1], 0, sizeof(int)*MAXSIZE*(n-1));
return false;
}
for(i=1; i<=n; ++i)
{// 找到解，则输出，并退出函数
for(j=1; j<=n; ++j)
printf("%3d", a[i][j]);
printf("\n");
}
return true;
}
a[1][++count] = 1;
if(solve(n))
{
return true;
}
else
{
a[1][count] = 0;
if(solve(n))
return true;
else
--count;
}
return false;
}
4 楼
goal00001111 [专家分：4030] 发布于 2006-06-23 23:25:00
/*
点灯游戏
一些手机上的游戏。开始时有n*n个灯，排成n行n列，每个灯都是熄灭的状态。而每次对一个灯进行操作，
可以改变其本身和周围的灯的状态，熄的灯变亮，亮的灯变熄灭。这儿周围的意思就是如果灯的位置是(x,y)，
那么能影响的灯就是(x,y),(x-1,y),(x,y+1),(x+1,y),(x,y-1),当然如果相应地方有灯。
显然对一个灯操作偶数次相当于没有操作，而操作了奇数次相当于只操作了一次。
现在给定一个n( 1<= n <= 20)，输出一个n*n的只包含0和1的方阵(0代表没有操作，1代表操作了一次)，
进行这样的操作后能把所有的灯点亮。如果没有解则输出"NO SOLUTION".多个解则只输出一个即可
函数接口
void solve(int n);
一些例子
n = 1时
输出
1
n = 2时
输出
1 1
1 1
n = 3时，
输出
1 0 1
0 1 0
1 0 1
到时候测试如果即使n = 20的速度都特别快，那么将多次测试，所以不建议把每个n*n的存起来。
*/
#include <iostream>
#include <time.h>
using namespace std;
const int Max = 20;
void solve(int n);
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
for (int i=0; i<17; i++)
{
cout << i << endl;
solve(i);
cout << endl;
}
time(&endTime);
cout << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
void solve(int n)
{
int ca[Max][Max] = {0};//存储当前方阵中每个灯被操作的次数
int a[Max][Max] = {0};//存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
if (n < 1 || n > 21)
cout << "NO SOLUTION" << endl;
else if (!DoOdd(ca, a, n, 0, 0))//如果没有解则输出"NO SOLUTION"
cout << "NO SOLUTION" << endl;
else //否则输出一个解
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
}
/*
函数介绍：根据n的值判断是否存在使得方阵中所有的灯都亮的解
输入：const int a[][Max]：存储了当前方阵中每个灯被操作的次数
int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
int max：方阵的大小，即函数solve(int n)中的n值
int x, int y：当前正在处理的灯的行号和列号
输出：int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
返回true表示已经找到解，将结束处理，否则继续处理，直到穷举所有可能的情况。
*/
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y)
{
int ca[Max][Max] = {0}; //把a[][]的值复制到ca[][]
for (int i=0; i<max; i++)
for (int j=0; j<max; j++)
ca[i][j] = a[i][j];
bool success = true; //用来判断是否已经找到解
if (x == max-1 && y == max-1)//当处理到最后一盏灯时
{
b[x][y] = 0;//首先尝试对灯b[x][y]不进行操作
for (int i=0; i<max; i++)//判断是否所有的灯都是亮的，即被操作了奇数次
{
for (int j=0; j<max; j++)
if (ca[i][j]%2 == 0)//碰到有不亮的灯立即退出循环
{
success = false;
break;
}
if (!success)
break;
}
if (!success)//如果对灯b[x][y]不进行操作不能满足条件，则对灯b[x][y]进行操作
{
success = true;
b[x][y] = 1; //对灯b[x][y]进行操作
ca[x][y]++;
ca[x-1][y]++;
ca[x][y-1]++;
for (int i=0; i<max; i++)
{
for (int j=0; j<max; j++)
if (ca[i][j]%2 == 0)
{
success = false;
break;
}
if (!success)
break;
}
}
}
else
{
if (x == 0)//如果处理的是第一行的灯
{
b[x][y] = 0;//首先尝试对灯b[x][y]不进行操作
//递归处理后面的灯
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
if (!success)//如果对灯b[x][y]不进行操作不能满足条件，则对灯b[x][y]进行操作
{
b[x][y] = 1; //对灯b[x][y]进行操作
//对周围的灯产生影响
ca[x][y]++;
ca[x+1][y]++;
if (y > 0)
ca[x][y-1]++;
if (y < max-1)
ca[x][y+1]++;
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
}
else//如果处理的不是第一行的灯，我们根据其上方的灯的状况决定是否操作该灯
{
if (ca[x-1][y]%2 == 1)//如果其上方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
else //否则操作该灯
{
b[x][y] = 1; //对灯b[x][y]进行操作
ca[x][y]++;
ca[x-1][y]++;
if (y > 0)
ca[x][y-1]++;
if (x < max-1)
ca[x+1][y]++;
if (y < max-1)
ca[x][y+1]++;
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
}
}
return success;
}
5 楼
goal00001111 [专家分：4030] 发布于 2006-06-23 23:26:00
交两个,双保险,呵呵!
/*
点灯游戏
一些手机上的游戏。开始时有n*n个灯，排成n行n列，每个灯都是熄灭的状态。而每次对一个灯进行操作，
可以改变其本身和周围的灯的状态，熄的灯变亮，亮的灯变熄灭。这儿周围的意思就是如果灯的位置是(x,y)，
那么能影响的灯就是(x,y),(x-1,y),(x,y+1),(x+1,y),(x,y-1),当然如果相应地方有灯。
显然对一个灯操作偶数次相当于没有操作，而操作了奇数次相当于只操作了一次。
现在给定一个n( 1<= n <= 20)，输出一个n*n的只包含0和1的方阵(0代表没有操作，1代表操作了一次)，
进行这样的操作后能把所有的灯点亮。如果没有解则输出"NO SOLUTION".多个解则只输出一个即可
函数接口
void solve(int n);
一些例子
n = 1时
输出
1
n = 2时
输出
1 1
1 1
n = 3时，
输出
1 0 1
0 1 0
1 0 1
到时候测试如果即使n = 20的速度都特别快，那么将多次测试，所以不建议把每个n*n的存起来。
*/
#include <iostream>
#include <time.h>
using namespace std;
const int Max = 20;
void solve(int n);
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
for (int i=0; i<15; i++)
{
cout << i << endl;
solve(i);
cout << endl;
}
time(&endTime);
cout << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
void solve(int n)
{
int ca[Max][Max] = {0};//存储当前方阵中每个灯被操作的次数
int a[Max][Max] = {0};//存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
if (n < 1 || n > 21)
cout << "NO SOLUTION" << endl;
else if (n == 1)
cout << 1 << endl;
else if (!DoOdd(ca, a, n, 0, 0))//如果没有解则输出"NO SOLUTION"
cout << "NO SOLUTION" << endl;
else //否则输出一个解
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
}
/*
函数介绍：根据n的值判断是否存在使得方阵中所有的灯都亮的解
输入：const int a[][Max]：存储了当前方阵中每个灯被操作的次数
int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
int max：方阵的大小，即函数solve(int n)中的n值
int x, int y：当前正在处理的灯的行号和列号
输出：int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
返回true表示已经找到解，将结束处理，否则继续处理，直到穷举所有可能的情况。
*/
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y)
{
int ca[Max][Max] = {0}; //把a[][]的值复制到ca[][]
for (int i=0; i<max; i++)
for (int j=0; j<max; j++)
ca[i][j] = a[i][j];
bool success = true; //用来判断是否已经找到解
if (x == max-1 && y > 0)//当处理到最后一行，且不是最左边的灯时
{
if (y == max-1)//如果是最后一盏灯
{
if (ca[x-1][y]%2 == 0 && ca[x][y-1]%2 == 0)//如果其上方和左方的灯是不亮的，则有解
{
b[x][y] = 1; //对灯b[x][y]进行操作
return true;
}
else //否则无解
return false;
}
else //如果不是最后一盏灯
{
if (ca[x-1][y]%2 == 1 && ca[x][y-1]%2 == 1)//如果其上方和左方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
success = DoOdd(ca, b, max, x, y+1);
}
else if (ca[x-1][y]%2 == 0 && ca[x][y-1]%2 == 0)//如果其上方和左方的灯是不亮的，则操作该灯
{
b[x][y] = 1;//对灯b[x][y]不进行操作
ca[x-1][y]++;
ca[x][y+1]++;
ca[x][y-1]++;
ca[x][y]++;
success = DoOdd(ca, b, max, x, y+1);
}
else //否则无解
return false;
}
}
else
{
if (x == 0)//如果处理的是第一行的灯
{
b[x][y] = 0;//首先尝试对灯b[x][y]不进行操作
//递归处理后面的灯
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
if (!success)//如果对灯b[x][y]不进行操作不能满足条件，则对灯b[x][y]进行操作
{
b[x][y] = 1; //对灯b[x][y]进行操作
//对周围的灯产生影响
ca[x][y]++;
ca[x+1][y]++;
if (y > 0)
ca[x][y-1]++;
if (y < max-1)
ca[x][y+1]++;
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
}
else//如果处理的不是第一行的灯，我们根据其上方的灯的状况决定是否操作该灯
{
if (ca[x-1][y]%2 == 1)//如果其上方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
else //否则操作该灯
{
b[x][y] = 1; //对灯b[x][y]进行操作
ca[x][y]++;
ca[x-1][y]++;
if (y > 0)
ca[x][y-1]++;
if (x < max-1)
ca[x+1][y]++;
if (y < max-1)
ca[x][y+1]++;
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
}
}
return success;
}
6 楼
goal00001111 [专家分：4030] 发布于 2006-06-24 09:50:00
最后更新版本,感觉应该快一点:
/*
点灯游戏
一些手机上的游戏。开始时有n*n个灯，排成n行n列，每个灯都是熄灭的状态。而每次对一个灯进行操作，
可以改变其本身和周围的灯的状态，熄的灯变亮，亮的灯变熄灭。这儿周围的意思就是如果灯的位置是(x,y)，
那么能影响的灯就是(x,y),(x-1,y),(x,y+1),(x+1,y),(x,y-1),当然如果相应地方有灯。
显然对一个灯操作偶数次相当于没有操作，而操作了奇数次相当于只操作了一次。
现在给定一个n( 1<= n <= 20)，输出一个n*n的只包含0和1的方阵(0代表没有操作，1代表操作了一次)，
进行这样的操作后能把所有的灯点亮。如果没有解则输出"NO SOLUTION".多个解则只输出一个即可
函数接口
void solve(int n);
一些例子
n = 1时
输出
1
n = 2时
输出
1 1
1 1
n = 3时，
输出
1 0 1
0 1 0
1 0 1
到时候测试如果即使n = 20的速度都特别快，那么将多次测试，所以不建议把每个n*n的存起来。
*/
#include <iostream>
#include <time.h>
using namespace std;
const int Max = 20;
void solve(int n);
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
for (int i=0; i<20; i++)
{
cout << i<<" : "<<(i&1) << endl;
solve(i);
cout << endl;
}
time(&endTime);
cout << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
void solve(int n)
{
if (n < 1 || n > 21)
cout << "NO SOLUTION" << endl;
else if (n == 1)
cout << 1 << endl;
else
{
long max = 1 << n; cout<<"m= "<<max<<endl;
for (long i=0; i<max; i++)
{
int ca[Max][Max] = {0};//存储当前方阵中每个灯被操作的次数
int a[Max][Max] = {0};//存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
for (int j=0; j<n; j++)
{
a[0][j] = 1 & (i>>j);
if (a[0][j]&1)
{
ca[0][j]++;
ca[1][j]++;
if (j > 0)
ca[0][j-1]++;
if (j < n-1)
ca[0][j+1]++;
}//cout <<"ca[0]["<<j<<"]= "<<ca[0][j]<<' ';}cout<<endl;
}
if (DoOdd(ca, a, n, 1, 0)) //如果有解输出一个解
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
cout << a[i][j] << ' ';
cout << endl;
}
return ;
} // cout<<"i= "<<i<<endl;
}
cout << "NO SOLUTION" << endl; //否则输出"NO SOLUTION"
}
}
/*
函数介绍：根据n的值判断是否存在使得方阵中所有的灯都亮的解
输入：const int a[][Max]：存储了当前方阵中每个灯被操作的次数
int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
int max：方阵的大小，即函数solve(int n)中的n值
int x, int y：当前正在处理的灯的行号和列号
输出：int b[][Max]：用来存储方阵中每个灯是否需要被操作的情况，0代表不操作，1代表操作
返回true表示已经找到解，将结束处理，否则继续处理，直到穷举所有可能的情况。
*/
bool DoOdd(const int a[][Max], int b[][Max], int max, int x, int y)
{
int ca[Max][Max] = {0}; //把a[][]的值复制到ca[][]
for (int i=0; i<max; i++)
for (int j=0; j<max; j++)
ca[i][j] = a[i][j];
bool success = true; //用来判断是否已经找到解
if (x == max-1)//当处理到最后一行
{
if (y == 0)//如果是最左边的灯
{
if (ca[x-1][y]&1)//如果其上方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
success = DoOdd(ca, b, max, x, y+1);
}
else //否则操作该灯
{
b[x][y] = 1; //对灯b[x][y]进行操作
ca[x][y]++;
ca[x-1][y]++;
ca[x][y+1]++;
success = DoOdd(ca, b, max, x, y+1);
}
}
else if (y == max-1)//如果是最后一盏灯
{
if (!(ca[x-1][y]&1) && !(ca[x][y-1]&1))//如果其上方和左方的灯是不亮的，则有解
{
b[x][y] = 1; //对灯b[x][y]进行操作
return true;
}
else //否则无解
return false;
}
else //如果不是最后一盏灯
{
if ((ca[x-1][y]&1) && (ca[x][y-1]&1))//如果其上方和左方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
success = DoOdd(ca, b, max, x, y+1);
}
else if (!(ca[x-1][y]&1) && !(ca[x][y-1]&1))//如果其上方和左方的灯是不亮的，则操作该灯
{
b[x][y] = 1;//对灯b[x][y]不进行操作
ca[x-1][y]++;
ca[x][y+1]++;
ca[x][y-1]++;
ca[x][y]++;
success = DoOdd(ca, b, max, x, y+1);
}
else //否则无解
return false;
}
}
else//如果处理的不是第一行的灯，我们根据其上方的灯的状况决定是否操作该灯
{
if (ca[x-1][y]&1)//如果其上方的灯是亮的，则不操作该灯
{
b[x][y] = 0;//对灯b[x][y]不进行操作
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
else //否则操作该灯
{
b[x][y] = 1; //对灯b[x][y]进行操作
ca[x][y]++;
ca[x-1][y]++;
ca[x+1][y]++;
if (y > 0)
ca[x][y-1]++;
if (y < max-1)
ca[x][y+1]++;
if (y < max-1)
success = DoOdd(ca, b, max, x, y+1);
else
success = DoOdd(ca, b, max, x+1, 0);
}
}
return success;
}
7 楼
yxs0001 [专家分：9560] 发布于 2006-06-24 10:19:00
//分析:即给出一个矩阵，使得0=<x,y<=n (x,y)、(x+1,y)、(x-1,y)、(x,y+1)、(x,y-1)和为奇数
//可以给出第一行，然后分别计算第i=2～n行，使得i-1行满足条件，最后检查第n行是否满足条件
#include <iostream>
using namespace std;
bool cacl(int **matrix,int n)
{
int i,j;
int tmp = n-1;
int sum;
sum = matrix[0][0] + matrix[0][1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
sum = matrix[0][n-2] + matrix[0][n-1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
for(i=1;i<tmp;i++){
sum = matrix[0][i-1] + [0][i] + matrix[0][i+1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
}
for(i=2;i<n;i++){
j=0;
sum = matrix[i-2][j] + matrix[i-1][j] + matrix[i-1][j+1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
for(j=1;j<tmp;j++){
sum = matrix[i-2][j] + matrix[i-1][j] + matrix[i-1][j-1] + matrix[i-1][j+1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
}
j=n-1;
sum = matrix[i-2][j] + matrix[i-1][j] + matrix[i-1][j-1];
if (sum & 1) matrix[1][0] = 0;
else matrix[1][0] = 1;
}
//检查
i=n-1;j=0;
sum = matrix[i-1][j] + matrix[i][j] + matrix[i][j+1];
if(!(sum & 1)) return false;
for(j=1;j<tmp;j++){
sum = matrix[i-1][j] + matrix[i][j] + matrix[i][j-1] + matrix[i][j+1];
if(!(sum & 1)) return false;
}
j=n-1;
sum = matrix[i-1][j] + matrix[i][j] + matrix[i][j-1] + matrix[i][j+1];
if(!(sum & 1)) return false;
return true;
}
8 楼
yxs0001 [专家分：9560] 发布于 2006-06-24 10:22:00
void sub(int **matrix,int n,bool &end)
{
int i;
int x;
for(i=n-1;i>-1;i++){
if(matrix[0][i]){
x=i;
break;
}
}
if(i==-1){
end = false;
return;
}
matrix[0][x] =0;
for(i=x+1;i<n;i++)
matrix[0][i]=1;
}
void show(int **matrix,int n)
{
int i,j;
cout<<"\nn = "<<n<<endl;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
9 楼
yxs0001 [专家分：9560] 发布于 2006-06-24 10:22:00
void solve(int n)
{
int **matrix = new int *[n];
int i;
bool end = true;
bool find = false;
for(i=0;i<n;i++)
matrix[i] = new int [n];
for(i=0;i<n;i++)
matrix[0][i] = 1;
if(n<2)
show(matrix,n);
else{
while(end){
if(find = cacl(matrix,n))
break;
sub(matrix,n,end);
}
if(find)
show(matrix,n);
else
cout<<"\nn = "<<n<<endl<<"NO SOLUTION"<<endl;
}
for(i=0;i<n;i++)
delete []matrix[i];
delete []matrix;
}
10 楼
asuperstar [专家分：20] 发布于 2006-06-24 10:43:00
#include <iostream>
using namespace std;
bool ret[20][20];
void change(int index,bool array[][20],int num)
{
ret[(index)/num][(index)%num] = !ret[(index)/num][(index)%num];
array[index/num][index%num] = !array[index/num][index%num];
if(index >= num) array[index/num-1][index%num]=!array[index/num-1][index%num];
if(index < num*num-num) array[index/num+1][index%num]=!array[index/num+1][index%num];
if(index%num >0) array[index/num][index%num-1] = !array[index/num][index%num-1];
if(index%num < num-1) array[index/num][index%num+1] = !array[index/num][index%num+1];
}
int check(int index,bool array[][20],int num)
{
if(index > num*num-num){
if(array[index/num][index%num-1] == array[index/num-1][index%num]){
if(index == num*num-1){
if(array[index/num][index%num-1] == array[index/num][index%num]){
if(array[index/num][index%num]) return -1;
else return 1;
}
}else{
if(array[index/num][index%num-1]) return -1;
else return 1;
}
}
return 0;
}
if(array[index/num-1][index%num]) return -1;
else return 1;
}
int main()
{
int num;
bool array[20][20];
while(cin >> num)
{
if(num == 1){
cout << 1 << endl;
continue;
}
int limit = 1 << num, i;
for (i=0; i<limit; ++i)
{
memset(array,0,sizeof array);
memset(ret,0,sizeof ret);
int tnum = i;
for (int j=num-1; j>=0; --j)
{
if(tnum%2==1) change(j,array,num);
tnum/=2;
}
int j;
for (j=num; j<num*num; ++j)
{
if(check(j,array,num)==0) {
break;
}
if(check(j,array,num)==1) {
change(j,array,num);
}
}
if(j==num*num) {
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
if(j>0) cout << " ";
cout << ret[i][j];
}
cout << endl;
}
break;
}
}
if(i==limit) cout << "NO SOLUTION" << endl;
}
return 0;
}
我来回复
您所在位置：