#include<bits/stdc++.h>
using namespace std;
#define g register
int heng[5];
int lst_heng[5];
int ans_heng[5];
int shu[5];
int lst_shu[5];
int ans_shu[5];
int xie_1;
int ans_xie_1;
int lst_xie_1;
int xie_2;
int ans_xie_2;
int lst_xie_2;
int t[5][5];
int book[5][5];
int if_n = 0;
struct node{
int x;
int y;
int maxn;
}que[20];
inline void dfs(int step)
{
if(if_n) return;
if(step == 17)
{
// if(xie_1 != ans_xie_1) return;
// if(xie_2 != ans_xie_2) return;
// for(int i = 1;i <= 4;++i)
// {
// if(heng[i] != ans_heng[i] || shu[i] != ans_shu[i]) return;
// }
for(int i = 1;i <= 4;++i)
{
for(int i1 = 1;i1 <= 4;++i1)
{
cout << t[i][i1] << " ";
}
cout << "\n";
}
if_n = 1;
return;
}
int x = que[step].x;
int y = que[step].y;
if(book[x][y])
{
dfs(step + 1);
return;
}
if(lst_xie_2 == 1 && x + y == 5)
{
int h = ans_xie_2 - xie_2;
if(h == 0) return;
if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
if(x == y && xie_1 + h > ans_xie_1) return;
if(x + y == 5 && xie_2 + h > ans_xie_2) return;
if(h + shu[y] > ans_shu[y]) return;
if(h + heng[x] > ans_heng[x]) return;
t[x][y] = h;
heng[x] += h;
shu[y] += h;
if(x == y) xie_1 += h;
if(x + y == 5) xie_2 += h;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
heng[x] -= h;
shu[y] -= h;
if(x == y) xie_1 -= h;
if(x + y == 5) xie_2 -= h;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
return;
}
if(lst_xie_1 == 1 && x == y)
{
int h = ans_xie_1 - xie_1;
if(h == 0) return;
if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
if(x == y && xie_1 + h > ans_xie_1) return;
if(x + y == 5 && xie_2 + h > ans_xie_2) return;
if(h + shu[y] > ans_shu[y]) return;
if(h + heng[x] > ans_heng[x]) return;
t[x][y] = h;
heng[x] += h;
shu[y] += h;
if(x == y) xie_1 += h;
if(x + y == 5) xie_2 += h;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
heng[x] -= h;
shu[y] -= h;
if(x == y) xie_1 -= h;
if(x + y == 5) xie_2 -= h;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
return;
}
if(lst_heng[x] == 1)
{
int h = ans_heng[x] - heng[x];
if(h == 0) return;
if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
if(x == y && xie_1 + h > ans_xie_1) return;
if(x + y == 5 && xie_2 + h > ans_xie_2) return;
if(h + shu[y] > ans_shu[y]) return;
if(h + heng[x] > ans_heng[x]) return;
t[x][y] = h;
heng[x] += h;
shu[y] += h;
if(x == y) xie_1 += h;
if(x + y == 5) xie_2 += h;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
heng[x] -= h;
shu[y] -= h;
if(x == y) xie_1 -= h;
if(x + y == 5) xie_2 -= h;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
return;
}
if(lst_shu[y] == 1)
{
int h = ans_shu[y] - shu[y];
if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
if(h == 0) return;
if(x == y && xie_1 + h > ans_xie_1) return;
if(x + y == 5 && xie_2 + h > ans_xie_2) return;
if(h + heng[x] > ans_heng[x]) return;
t[x][y] = h;
heng[x] += h;
shu[y] += h;
if(x == y) xie_1 += h;
if(x + y == 5) xie_2 += h;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
heng[x] -= h;
shu[y] -= h;
if(x == y) xie_1 -= h;
if(x + y == 5) xie_2 -= h;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
return;
}
// if(x > 1 && y == 1)
// {
// if(heng[x - 1] != ans_heng[x - 1]) return;
// }
// if(x == 4)
// {
// if(y > 1)
// {
// if(xie_2 != ans_xie_2) return;
// if(shu[y - 1] != ans_shu[y - 1]) return;
// }
// }
// if(y == 4 && x != 4)
// {
// int h = ans_heng[x] - heng[x];
// if(h == 0) return;
// if(if_n) return;
// if(shu[y] + h > ans_shu[y]) return;
// if(x == y && xie_1 + h > ans_xie_1) return;
// if(x + y == 5 && xie_2 + h > ans_xie_2) return;
// t[x][y] = h;
// heng[x] += h;
// shu[y] += h;
// if(x == y) xie_1 += h;
// if(x + y == 5) xie_2 += h;
// dfs(step + 1);
// t[x][y] = 0;
// heng[x] -= h;
// shu[y] -= h;
// if(x == y) xie_1 -= h;
// if(x + y == 5) xie_2 -= h;
// return;
// }
// if(x == 4 && y != 4)
// {
// int h = ans_shu[y] - shu[y];
// if(h == 0) return;
// if(if_n) return;
// if(heng[x] + h > ans_heng[x]) return;
// if(x == y && xie_1 + h > ans_xie_1) return;
// if(x + y == 5 && xie_2 + h > ans_xie_2) return;
// t[x][y] = h;
// heng[x] += h;
// shu[y] += h;
// if(x == y) xie_1 += h;
// if(x + y == 5) xie_2 += h;
// dfs(step + 1);
// t[x][y] = 0;
// heng[x] -= h;
// shu[y] -= h;
// if(x == y) xie_1 -= h;
// if(x + y == 5) xie_2 -= h;
// return;
// }
// if(x == 4 && y == 4)
// {
// int h = ans_heng[x] - heng[x];
// if(h == 0) return;
// if(h != ans_shu[y] - shu[y]) return;
// if(h != ans_xie_1 - xie_1) return;
//
// t[x][y] = h;
// heng[x] += h;
// shu[y] += h;
// if(x == y) xie_1 += h;
// if(x + y == 5) xie_2 += h;
// dfs(step + 1);
// t[x][y] = 0;
// heng[x] -= h;
// shu[y] -= h;
// if(x == y) xie_1 -= h;
// if(x + y == 5) xie_2 -= h;
// return;
// }
int up = min(ans_heng[x] - heng[x],ans_shu[y] - shu[y]);
up = min(up,que[step].maxn);
if(up == 0) return;
int mid = up / 3;
for(g int i = mid + 1;i <= up / 3 * 2;++i)
{
if(i == 0) continue;
if(if_n) return;
if(heng[x] + i > ans_heng[x]) continue;
if(shu[y] + i > ans_shu[y]) continue;
if(x == y && xie_1 + i > ans_xie_1) continue;
if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
t[x][y] = i;
heng[x] += i;
shu[y] += i;
if(x == y) xie_1 += i;
if(x + y == 5) xie_2 += i;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
t[x][y] = 0;
heng[x] -= i;
shu[y] -= i;
if(x == y) xie_1 -= i;
if(x + y == 5) xie_2 -= i;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
}
for(g int i = mid;i >= 1;--i)
{
if(i == 0) continue;
if(if_n) return;
if(heng[x] + i > ans_heng[x]) continue;
if(shu[y] + i > ans_shu[y]) continue;
if(x == y && xie_1 + i > ans_xie_1) continue;
if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
t[x][y] = i;
heng[x] += i;
shu[y] += i;
if(x == y) xie_1 += i;
if(x + y == 5) xie_2 += i;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
t[x][y] = 0;
heng[x] -= i;
shu[y] -= i;
if(x == y) xie_1 -= i;
if(x + y == 5) xie_2 -= i;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
}
for(g int i = up / 3 * 2 + 1;i <= up;++i)
{
if(i == 0) continue;
if(if_n) return;
if(heng[x] + i > ans_heng[x]) continue;
if(shu[y] + i > ans_shu[y]) continue;
if(x == y && xie_1 + i > ans_xie_1) continue;
if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
t[x][y] = i;
heng[x] += i;
shu[y] += i;
if(x == y) xie_1 += i;
if(x + y == 5) xie_2 += i;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
dfs(step + 1);
t[x][y] = 0;
heng[x] -= i;
shu[y] -= i;
if(x == y) xie_1 -= i;
if(x + y == 5) xie_2 -= i;
lst_heng[x]++;
lst_shu[y]++;
if(x == y) lst_xie_1++;
if(x + y == 5) lst_xie_2++;
}
}
inline bool cmp(node x,node y)
{
return x.maxn > y.maxn;
}
int main()
{
// freopen("scrab.in","r",stdin);
// freopen("scrab.out","w",stdout);
std::ios::sync_with_stdio(false);
for(g int i = 1;i <= 4;++i) cin >> ans_heng[i],lst_heng[i] = 4;
for(g int i = 1;i <= 4;++i) cin >> ans_shu[i],lst_shu[i] = 4;
lst_xie_1 = lst_xie_2 = 4;
cin >> ans_xie_1;
cin >> ans_xie_2;
for(g int i = 1,x,y,z;i <= 4;++i)
{
cin >> x >> y >> z;
x++;
y++;
t[x][y] = z;
book[x][y] = 1;
heng[x] += z;
shu[y] += z;
if(x == y) xie_1 += z;
if(x + y == 5) xie_2 += z;
lst_heng[x]--;
lst_shu[y]--;
if(x == y) lst_xie_1--;
if(x + y == 5) lst_xie_2--;
}
for(g int i = 1;i <= 4;++i)
{
for(g int i1 = 1;i1 <= 4;++i1)
{
int num = (i - 1) * 4 + i1;
que[num].x = i;
que[num].y = i1;
que[num].maxn = max(ans_heng[i] - heng[i],ans_shu[i1] - shu[i1]);
if(i == i1)
{
que[num].maxn = max(que[num].maxn,ans_xie_1 - xie_1);
}
if(i + i1 == 5)
{
que[num].maxn = max(que[num].maxn,ans_xie_2 - xie_2);
}
}
}
sort(que + 1,que + 1 + 16,cmp);
dfs(1);
return 0;
}
无论如何修改mid都会至少有一个点TLE,还是不一样的点T_T
请求巨巨巨巨巨佬帮助!!!!!QAQ
