0基础学网站设计,台州市建设规划局网站班子成员,wordpress 网校主题,建设单位适合去哪个网站看资料题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id2003 题解 考虑搜索。 确定了第一行和第一列#xff0c;那么就确定了整个矩阵#xff0c;因此搜索的范围可以降到399个位置。 首先搜索第一行#xff0c;显然每个不是第一行第一列的位置都可以由三个位置唯一确定… 题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id2003 题解 考虑搜索。 确定了第一行和第一列那么就确定了整个矩阵因此搜索的范围可以降到399个位置。 首先搜索第一行显然每个不是第一行第一列的位置都可以由三个位置唯一确定(1,1),(1,i),(j,1)(1,1),(1,i),(j,1)(1,1),(1,i),(j,1)。由于搜索的是第一行可以把(i,j)(i,j)(i,j)这个位置000和p−1p-1p−1都带入一遍得到的结果就是(j,1)(j,1)(j,1)的上下界。如果搜索的过程中发现冲突了那么说明第一行这样填不行剪枝。 代码 #include cstdio
#include algorithmint read()
{int x0,f1;char chgetchar();while((ch0)||(ch9)){if(ch-){f-f;}chgetchar();}while((ch0)(ch9)){xx*10ch-0;chgetchar();}return x*f;
}const int maxn200;int n,m,p,a[maxn10][maxn10],l[maxn10][maxn10],r[maxn10][maxn10];int f(int x)
{return (x1)?1:-1;
}int search(int y)
{if(ym){return 1;}for(a[1][y]0; a[1][y]p; a[1][y]){int flag1;for(int i2; in; i){int b(0-a[1][1]*f(iy)-a[1][y]*f(i)-a[i][y])*f(y),c((p-1)-a[1][1]*f(iy)-a[1][y]*f(i)-a[i][y])*f(y);if(bc){std::swap(b,c);}l[y][i]std::max(l[y-1][i],b);r[y][i]std::min(r[y-1][i],c);if(l[y][i]r[y][i]){flag0;break;}}if(flag){if(search(y1)){return 1;}}}return 0;
}int main()
{nread();mread();pread();for(int i1; in; i){for(int j1; jm; j){a[i][j]read();}}for(int i2; in; i){for(int j2; jm; j){a[i][j]-a[i-1][j]a[i][j-1]a[i-1][j-1];}}for(int i2; in; i){l[1][i]0;r[1][i]p-1;}for(a[1][1]0; a[1][1]p; a[1][1]){if(search(2)){for(int i1; in; i){for(int j1; jm; j){if(i1){printf(%d%c,a[i][j],(jm)?\n: );}else if(j1){printf(%d%c,l[m][i],(jm)?\n: );}else{printf(%d%c,a[i][j]a[1][1]*f(ij)a[1][j]*f(i)l[m][i]*f(j),(jm)?\n: );}}}return 0;}}return 0;
}转载于:https://www.cnblogs.com/Canopus-wym/p/10376135.html
