算法分析与设计 西工大 noj 第二次实验
Problem A 0-1背包问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。
输入：
多个测例，每个测例的输入占三行。第一行两个整数：n（n<=10）和c，第二行n个整数分别是w1到wn，第三行n个整数分别是p1到pn。
n 和 c 都等于零标志输入结束。
输出：
每个测例的输出占一行，输出一个整数，即最佳装载的总价值。
输入样例：
1 2
1
1
2 3
2 2
3 4
0 0
输出样例：
1
4
这是一道典型的01背包。由于n十分小，所以可以采用暴力搜索，也可以采用DP。
其实严格意义上我完全可以把物品的价值搞成1e9，这样就不可以使用DP了，但是数据十分水，也就过去了。
标准解法是暴力
#include <iostream>
#include <cstdio>
using namespace std;
#define N 20
int n, m;
int w[N], v[N];
int ans = 0;
inline int max(int x, int y)
{
return x > y ? x : y;
}
void dfs(int x, int sw, int sv)
{
if(x > n) {
ans = max(ans, sw);
return;
}
dfs(x+1, sw, sv);
if(sv + v[x] <= m){
dfs(x+1, sw + w[x], sv+v[x]);
}
}
int main()
{
while(scanf("%d%d", &n, &m), n||m)
{
ans = 0;
for(int i = 1; i <= n; i++) scanf("%d", v+i);
for(int i = 1; i <= n; i++) scanf("%d", w+i);
dfs(1, 0, 0);
printf("%d\n", ans);
}
return 0;
}
Problem B 装载问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。
输入：
多个测例，每个测例的输入占两行。第一行一次是c1、c2和n（n<=10）；第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。
输出：
对于每个测例在单独的一行内输出Yes或No。
输入样例：
7 8 2
8 7
7 9 2
8 8
0 0 0
输出样例：
Yes
No
其实本质上还是一道背包问题。
把第一个小船当成背包，在不超载的前提下放置尽可能重的物品，以便于为第二艘小船留下余地。
#include<iostream>
#include<cstdio>
using namespace std;
#define N 20
int c1, c2, n;
int w[N];
int sum;
bool flag = false;
void dfs(int x, int s)
{
if(x > n){
if(s <= c1 && (sum - s) <= c2) flag = true;
return ;
}
dfs(x+1, s);
dfs(x+1, s+w[x]);
}
int main()
{
while(scanf("%d%d%d", &c1, &c2, &n), n)
{
flag = false;
sum = 0;
for(int i = 1; i <= n; i++) scanf("%d", w+i);
for(int i = 1; i <= n; i++) sum += w[i];
dfs(1, 0);
if(flag)
{
puts("Yes");
}
else
{
puts("No");
}
}
return 0;
}
Problem C 堡垒问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。
输入：
每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。n等于0标志输入结束。
输出：
每个测例在单独的一行输出一个整数：最多修建堡垒的个数。
输入样例：
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
输出样例：
5
1
5
2
4
#include <cstdio>
#include <cstdlib>
using namespace std;
#define N 6
char a[N][N];
int n;
int ans = 0;
inline void get(int val, int &x, int &y)
{
x = val/n;
y = val%n;
}
bool ck(int x, int y)
{
for(int i = x+1; i < n; i++){
if(a[i][y] == 'o') return 0;
else if(a[i][y] == 'X') break;
}
for(int i = x-1; i >= 0; i--){
if(a[i][y] == 'o') return 0;
else if(a[i][y] == 'X') break;
}
for(int i = y+1; i< n; i++){
if(a[x][i] == 'o') return 0;
else if(a[x][i] == 'X') break;
}
for(int i = y-1; i >= 0; i--){
if(a[x][i] == 'o') return 0;
else if(a[x][i] == 'X') break;
}
return true;
}
void dfs(int p, int s)
{
if(p >= n*n){
if(s > ans) ans = s;
//DEBUG
/*
if(s == 4){
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
printf("%c", a[i][j]);
}
puts("");
}
puts("");
}
*/
//ENDDEBUG
return ;
}
dfs(p+1, s);
int x, y;
get(p, x, y);
if(ck(x, y) && a[x][y] == '.')
{
a[x][y] = 'o';
dfs(p+1, s+1);
a[x][y] = '.';
}
}
int main()
{
while(scanf("%d", &n), n){
for(int i = 0; i < n; i++) scanf("%s", a[i]);
ans = 0;
dfs(0, 0);
printf("%d\n", ans);
}
// n = 4;
// for(int i = 0; i < 16; i++)
// {
// int x, y;;
// get(i, x, y);
// printf("(%d, %d) ", x, y);
// }
}
Problem D 8皇后问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
输出8皇后问题所有结果。
输入：
没有输入。
输出：
每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，‘A’表示皇后，‘.’表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。
输入样例：
无
输出样例：
输出的前几行：
No 1:
A.......
....A...
.......A
.....A..
..A.....
......A.
.A......
...A....
No 2:
A.......
.....A..
.......A
..A.....
......A.
...A....
.A......
....A...
这一道题目所使用的数据结构十分巧妙，由于每一行仅仅只可以有一个皇后，所以采用一维数组就可以。
注意时时刻刻想着剪枝。
判断对角线的方法是：abs(stac[i] - val) == abs(i-row)
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 12
int stac[N];
int cnt = 0;
bool ck(int row, int val)
{
for(int i = 1; i <= 8; i++)
{
if(stac[i] == 0 || i == row) continue;
if(stac[i] == val || abs(stac[i] - val) == abs(i-row)) return false;
}
return true;
}
inline void Print(int x)
{
for(int i = 1; i < x; i++) putchar('.');
putchar('A');
for(int i = x+1; i <= 8; i++) putchar('.');
puts("");
}
void dfs(int x)
{
if(x > 8)
{
printf("No %d:\n", ++cnt);
for(int i = 1; i <= 8; i++)
{
Print(stac[i]);
}
return;
// for(int i = 1; i <= 8; i++) printf("%d ", stac[i]);
//balabala
//return ;
//DEBUG
// exit(0);
}
for(int i = 1; i <= 8; i++)
{
if(ck(x, i)) {
stac[x] = i;
dfs(x+1);
stac[x] = 0;
}
}
}
int main()
{
dfs(1);
return 0;
}
Problem E 素数环问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
把1到20这重新排列，使得排列后的序列A满足：
a. 任意相邻两个数之和是素数
b. 不存在满足条件a的序列B使得：A和B的前k（0 <= k <= 19）项相同且B的第k+1项比A的第k+1项小。(即按字典序排列的第一项)
输入：
没有输入。
输出：
输出A，两个数字之间用一个空格隔开，第一个数字前面和最后一个数字后面没有空格。
输入样例：
输出样例：
标准解法
如果要是要求输出所有的素数环，那么就应该采用求全排列+剪枝+判断字典序
贪心解法
但是可以使用贪心来做。从前往后先试1，然后再试2...如果找到满足条件的环，就直接输出。
打表解法
这么小的数据量，直接人脑使用贪心法进行计算，来一个puts("")
//采取贪心的思想，从小到大选择
#include <cstdio>
#include <cstdlib>
using namespace std;
#define N 25
bool v[N];
int stac[N];
bool prim[40];
void dfs(int x)
{
if(x > 20)
{
for(int i = 1; i <= 20; i++) {
if(i != 20)
printf("%d ", stac[i]);
else printf("%d", stac[20]);
}
puts("");
exit(0);
}
for(int i = 1; i <= 20; i++)
{
if(!v[i] && (x == 1 || x < 20 && x > 1 && (prim[stac[x-1] + i]) ||(x == 20 && (prim[stac[1] + i]))))
{
stac[x] = i;
v[i] = 1;
dfs(x+1);
v[i] = 0;
stac[x] = 0;
}
}
}
int main()
{
for(int i = 2; i <= 45; i++)
{
bool flag = true;
for(int j = 2; j*j <= i; j++) if(i % j == 0){
flag = false;
break;
}
if(!flag) prim[i] = 0;
else prim[i] = 1;
}
dfs(1);
// for(int i = 1; i <= 45; i++) if(prim[i])
// printf("%d ", i);
return 0;
}
Problem F 迷宫问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。
输入：
多个测例。输入的第一行是一个整数n，表示测例的个数。接下来是n个测例，每个测例占21行，第一行四个整数x1，y1，x2，y2是起止点的位置（坐标从零开始），（x1，y1）是起点，（x2，y2）是终点。下面20行每行20个字符，’.’表示空格；’X’表示墙。
输出：
每个测例的输出占一行，输出Yes或No。
输入样例：
2
0 0 19 19
....................
XXXXXXXXXXXXXXXXXXXX
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
0 0 19 19
....................
XXXXXXXXXXXXXXXXXXX.
....................
.XXXXXXXXXXXXXXXXXXX
....................
XXXXXXXXXXXXXXXXXXX.
....................
.XXXXXXXXXXXXXXXXXXX
....................
XXXXXXXXXXXXXXXXXXX.
....................
.XXXXXXXXXXXXXXXXXXX
....................
XXXXXXXXXXXXXXXXXXX.
XXXXXXXXXXXXXXXXXXX.
XXXXXXXXXXXXXXXXXXX.
XXXXXXXXXXXXXXXXXXX.
....................
.XXXXXXXXXXXXXXXXXXX
....................
输出样例：
No
Yes
直接进行DFS图的遍历
#include <iostream>
#include <cstdio>
using namespace std;
#define N 30
pair<int, int> s, t;
char a[N][N];
bool v[N][N];
const int n = 20;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
inline bool ck(int x, int y)
{
if(x < 0 || x >= n || y < 0 || y >= n) return false;
if(v[x][y]) return false;
if(a[x][y] == 'X') return false;
return true;
}
bool dfs(int nx, int ny)
{
if(nx == t.first && ny == t.second){
return 1;
}
for(int k = 0; k < 4; k++)
{
int x = nx + dx[k];
int y = ny + dy[k];
if(ck(x, y))
{
v[x][y] = 1;
if(dfs(x, y)) return 1;
}
}
return 0;
}
int main()
{
int T;
cin >> T;
while(T--)
{
for(int i = 0; i <= 20; i++)
for(int j = 0; j <= 20; j++)
v[i][j] = false;
scanf("%d%d%d%d", &s.first, &s.second, &t.first, &t.second);
for(int i = 0; i < n; i++) scanf("%s", a[i]);
if(dfs(s.first, s.second))
{
puts("Yes");
}
else
{
puts("No");
}
}
return 0;
}
Problem G 踩气球
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。
输入：
输入为两个数字，0 0表示结束；
输出：
输出为获胜的数字。
输入样例：
36 62
49 343
0 0
输出样例：
62
49
这一道题目使我畏惧，真的是太太太离谱了！
暴力搜索法：
虽然看起来有很多情况，但是由于int范围内的相乘大于int的数字其实并没有多少，所以也还可以
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int small, big;//大的数字以及小的数字
int mul1, mul2;//已经当前已经踩过的气球的乘积
bool f1, f2;//记录说的是不是真话
void dfs(int k)
{
if(k <= 1){
if(mul1 == small && mul2 == big) {
f1 = 1, f2 = 1;
}
else if( (!f1 || !f2) && mul1 == small ){
f1 = 1, f2 = 0;
}
else if(!f1&&!f2&&mul2 == big){
f1 = 0, f2 = 1;
}
return ;
}
if(mul1*k <= small && small % k == 0){
mul1 *= k;
dfs(k-1);
mul2 /= k;
}
if(mul2 * k <= big && big % k == 0){
mul2 *= k;
dfs(k-1);
mul2 /= k;
}
dfs(k-1);
}
int main()
{
while(scanf("%d%d", &big, &small), big || small){
if(small > big) swap(small, big);
mul1 = 1, mul2 = 1;
f1 = 0, f2 = 0;
dfs(100);
if(f1 && f2 || !f1 && !f2){
printf("%d\n", big);
}
else{
if(f1) printf("%d\n", small);
else printf("%d\n", big);
}
}
//cout << f1 << f2;
return 0;
}
Problem H 字母转换
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:
[
i i i i o o o o
i o i i o o i o
]
输入：
给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。
输出：
所有的进栈和出栈序列,输出结果需满足字典序
输入样例：
madam
adamm
bahama
bahama
long
short
eric
rice
输出样例：
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]
#include <cstdio>
#include <iostream>
#include <stack>
#include <cstring>
#include <vector>
using namespace std;
#define N 100005
char a[N], b[N];
stack<char> st;
vector<char> op;
int p = 1;
int q = 1;
int len = 0;
void dfs(int n)
{
if(n > 2 * len)
{
for(int i = 0; i < op.size(); i++)
{
if(i != op.size() - 1)
printf("%c ", op[i]);
else
printf("%c", op[i]);
}
puts("");
return;
}
if(p <= len)
{
op.push_back('i');
st.push(a[p]);
p++;
dfs(n+1);
op.pop_back();
st.pop();
p--;
}
if(st.size() && st.top() == b[q])
{
op.push_back('o');
char tmp = st.top();
st.pop();
q++;
dfs(n+1);
q--;
st.push(tmp);
op.pop_back();
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%s%s", a+1, b+1) != EOF)
{
int len1 = strlen(a+1);
int len2 = strlen(b+1);
if(len1 != len2){
printf("[\n]\n");
continue;
}
len = len1;
printf("[\n");
dfs(1);
printf("]\n");
}
return 0;
}
Problem I 农场灌溉问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。
输入：
给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图
输出：
编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。
输入样例：
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1
输出样例：
2
3
简直是带模拟
需要注意判断可达性的时候，不仅仅与当前的格子有关系，并且与其他的格子有关系。
#include <iostream>
#include <cstdio>
using namespace std;
bool th[128][5];
int n,m;
char a[100][100];
bool v[100][100];
void init();
void dfs(int x, int y)
{
v[x][y] = 1;
int r, c;
//0
r = x, c = y-1;
if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){
if(th[a[x][y]][0] && th[a[r][c]][2]){
dfs(r, c);
}
}
//1
r = x-1, c = y;
if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){
if(th[a[x][y]][1] && th[a[r][c]][3]){
dfs(r, c);
}
}
//2
r = x, c = y+1;
if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){
if(th[a[x][y]][2] && th[a[r][c]][0]){
dfs(r, c);
}
}
//3
r = x+1, c = y;
if(r >= 1 && r <= n && c >= 1 && c <= m && !v[r][c]){
if(th[a[x][y]][3] && th[a[r][c]][1]){
dfs(r, c);
}
}
}
int main()
{
init();
while(scanf("%d%d", &n, &m), n!=-1 || m!=-1)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
v[i][j] = 0;
for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(!v[i][j]) {
dfs(i, j);
ans ++;
}
}
printf("%d\n", ans);
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= m; j++)
// cout << a[i][j];
// puts("");
// }
}
return 0;
}
void init()
{
th['A'][0] = 1;
th['A'][1] = 1;
th['B'][1] = 1;
th['B'][2] = 1;
th['C'][0] = 1;
th['C'][3] = 1;
th['D'][2] = 1;
th['D'][3] = 1;
th['E'][1] = 1;
th['E'][3] = 1;
th['F'][0] = 1;
th['F'][2] = 1;
th['G'][0] = 1;
th['G'][1] = 1;
th['G'][2] = 1;
th['H'][0] = 1;
th['H'][1] = 1;
th['H'][3] = 1;
th['I'][0] = 1;
th['I'][2] = 1;
th['I'][3] = 1;
th['J'][1] = 1;
th['J'][2] = 1;
th['J'][3] = 1;
th['K'][0] = 1;
th['K'][1] = 1;
th['K'][2] = 1;
th['K'][3] = 1;
}
Problem J 求图像的周长
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。
输入：
首先给出m、n、x、y四个正整数，下面给出m×n的图形，x、y表示点击的位置，全0表示结束。
输出：
点击的图形的周长。
输入样例：
2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...
0 0 0 0
输出样例：
8
18
#include <iostream>
#include <cstdio>
using namespace std;
#define N 10005
int n, m, sx, sy;
char a[N][N];
bool v[N][N];
int ans = 0;
int dx[8] = {-1, -1, -1 ,0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int lenth(int nx, int ny)
{
int all = 4;
static const int qx[4] = {-1, 0, 0, 1};
static const int qy[4] = {0, -1, 1, 0};
for(int k = 0; k < 4; k++)
{
int x = nx + qx[k];
int y = ny + qy[k];
if(x < 1 || x > n || y < 0 || y > m) continue;
if(a[x][y] == 'X')all --;
}
return all;
}
void dfs(int nx, int ny)
{
v[nx][ny] = 1;
ans += lenth(nx, ny);
for(int k = 0; k < 8; k++)
{
int x = dx[k] + nx;
int y = dy[k] + ny;
if(v[x][y]) continue;
if(a[x][y] != 'X') continue;
dfs(x, y);
}
}
int main()
{
while(scanf("%d%d%d%d", &n, &m, &sx, &sy), n || m || sx || sy)
{
for(int i = 1; i <= n; i++) scanf("%s", a[i]+1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
v[i][j] = 0;
ans = 0;
dfs(sx, sy);
printf("%d\n", ans);
}
return 0;
}
Problem K 图的m着色问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。
输入：
第1行有3个正整数n，r 和m（n < 20,r < 200,m < 10），表示给定的图G有n个顶点和r条边，m种颜色。顶点编号为0，1，2，…，n-1。接下来的r行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。
输出：
输出不同的着色方案的总数。
输入样例：
3 2 2
0 1
1 2
输出样例：
2
#include <iostream>
#include <cstdio>
using namespace std;
#define N 25
int a[N][N];
int c[N];
int n, r, m;
int ans = 0;
inline bool ck(int x, int val)
{
for(int y = 1; y < x; y++)
{
if(!a[x][y]) continue;
if(val == c[y]) return 0;
}
return true;
}
void dfs(int x)
{
if(x > n){
ans ++;
// for(int i = 1; i <= n; i++) printf("%d ", c[i]);
// puts("");
return;
}
for(int i = 1; i <= m; i++)
{
if(ck(x, i)) {
c[x] = i;
dfs(x+1);
c[x] = 0;//浅浅回复一下
}
}
}
int main()
{
scanf("%d%d%d", &n, &r, &m);
for(int i = 1; i <= r; i++)
{
int u, v;
scanf("%d%d", &u, &v);
u++, v++;
a[u][v] = 1;
a[v][u] = 1;
}
dfs(1);
printf("%d\n", ans);
return 0;
}
Problem L 三阶幻方
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
三阶幻方是最简单的幻方，又叫九宫格，是由1,2,3,4,5,6,7,8,9九个数字组成的一个三行三列的矩阵，其对角线、横行、纵向的的和都为15。
输入：
无
输出：
按字典序输出所有的满足条件的幻方矩阵，每两个数字之间带一个空格，行尾无空格，每个幻方后带一个空行。
无输入以及输出样例
//幻方！都可以幻方！！！！
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
bool v[12];
int a[4][4];
inline bool judge(int x, int y, int val)
{
//DEBUG
//return true;
int sum = 0;
if(x == 0 && y == 2){
for(int i = 0; i < 3; i++) sum += a[0][i];
if(sum == 15) return true;
else return false;
}
if(x == 1 && y == 2){
for(int i = 0; i < 3; i++) sum += a[1][i];
if(sum == 15) return true;
else return false;
}
if(x == 2 && y == 0)
{
int s1 = 0, s2 = 0;;
for(int i = 0; i < 3; i++) s1 += a[i][0];
s2 += a[0][2] + a[1][1] + a[2][0];;
if(s2 == 15 && s1 == 15) return true;
else return false;
}
if(x == 2 && y == 1){
for(int i = 0; i < 3; i++) sum += a[i][1];
if(sum == 15) return true;
else return false;
}
if(x == 2 && y == 2){
int s1 = 0, s2 = 0, s3 = 0;
for(int i = 0; i < 3; i ++) s1 += a[i][2];
for(int i = 0; i < 3; i ++) s2 += a[i][i];
for(int i = 0; i < 3; i ++) s3 += a[2][i];
if(s1 == 15 && s2 == 15 && s3 == 15) return true;
else return false;
}
return true;
}
//int dede = 0;
void dfs(int p)
{
if(p >= 3*3)
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(j < 2)
printf("%d ", a[i][j]);
else
printf("%d", a[i][j]);
}
puts("");
}
puts("");
//if(++dede >= 5) exit(0);
}
int nx = p/3;
int ny = p%3;
for(int i = 1; i <= 9; i++)
{
a[nx][ny] = i;
if(judge(nx, ny, i) && !v[i]){
v[i] = 1;
dfs(p+1);
v[i] = 0;
}
a[nx][ny] = 0;
}
}
int main()
{
dfs(0);
return 0;
}