【补题】Xi‘an Invitational 2023 E. Merge the Rectangles

题意：给个矩形，然后在里面画很多条线，将矩阵分割，包管分割出来的图案肯定是矩形，至于n，m矩阵这里不多赘述，题意就是这样，假如不记得了请转至原题
原题链接：Merge the Rectangles - Problem - QOJ.ac
 
思路：
1.首先得知分割出来的图案是矩形，这一点很紧张，这实在影响背面结论的得出
2.到底是什么样的矩形才能归并，为什么第二个样例只要长成那样没有任何时机归并？不妨反着思考，一个能归并的矩形是怎么创造出来的。
实在光看样例会有点感觉，再玩玩更有感觉了，No的样例好像好像缺了一条完备的穿越列大概行的线，当然这是我vp时个人思路不影响整个题解
假如我们造出来的矩形肯定能归并是什么样子的？没错，就是把在分割出来的矩形，再画一条笔直贯穿的线，有并且肯定是笔直的，因为弯曲的线会导致分割出来的图形不是矩形，所以这道题任何一条分割线都是直线，这给了我们dfs去快速询问每一条边的时机。
为什么用dfs？因为假如当前分割出来的矩形是可归并的，这代表着有那么一条线出现在矩形中并且会贯穿这一整个矩形，那么实在我们要求矩阵中的任何一条线是否是由边界大概上一条分割线而来的。

图中可以归并我是怎么画出来的

综上代码的写法就很明确了，因为有01值，利用前缀和判断这条线是否成功贯穿了当前矩形，假如没贯穿但是有线的存在，得记录下来这里大概是导致无法归并的缘故原由（无法归并就是凭空在当前矩形里挖了一块，看一下样例就知道了，是凭空捏出来的，凑出来的矩形）
假如贯穿了，那么根据这条线所新分割出来的矩形，仿照上面递归去询问其他的线是精确划分矩形的方式吗
代码：

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. #define endl '\n'
5. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
6. const int N = 1e6+10;
7. const int INF = 1e12;
8. const int MOD = 998244353;
10. int y[1505][1505];//横着
11. int x[1505][1505];//竖着
13. int dfs(int x1,int y1,int x2,int y2){
14.         int sum=0;
15.        
16.         for(int i=x1+1;i<x2;i++){
17.                 if( y[i][y2-1]-y[i][y1-1]==y2-y1 ){
18.                         return dfs(x1,y1,i,y2) && dfs(i,y1,x2,y2);
19.                 }
20.                 sum+=y[i][y2-1]-y[i][y1-1];
21.         }
22.        
23.         for(int i=y1+1;i<y2;i++){
24.                 if( x[x2-1][i]-x[x1-1][i]==x2-x1 ){
25.                         return dfs(x1,y1,x2,i) && dfs(x1,i,x2,y2);
26.                 }
27.                 sum+=x[x2-1][i]-x[x1-1][i];
28.         }
29.        
30.         if(!sum) return 1;
31.         return 0;
32.        
33. }
35. void solve(){
36.         int n,m;
37.         cin >> n >> m;
38.        
39.         for(int i=2;i<=n;i++){
40.                 for(int j=1;j<=m;j++){
41.                         char c;
42.                         cin >> c;
43.                         y[i][j]+=(c-'0');
44.                         y[i][j]+=y[i][j-1];
45.                 }
46.         }
47.        
48.         for(int i=1;i<=n;i++){
49.                 for(int j=2;j<=m;j++){
50.                         char c;
51.                         cin >> c;
52.                         x[i][j]+=(c-'0');
53.                         x[i][j]+=x[i-1][j];
54.                 }
55.         }
56.        
57.         if(dfs(1,1,n+1,m+1)) cout << "YES" << endl;
58.         else cout << "NO" << endl;
59.        
60. }
62. signed main() {
63.         IOS;
64.        
65.         int t = 1;
66. //        cin >> t;
67.         while (t--) {
68.                 solve();
69.         }
70.        
71. }

复制代码

个人感觉这道又是逆向思维的体现，实在只要倒过来想，就会发现矩阵是否能成功归并很简单
参考了qoj一个人的题解：Submission #196363 - QOJ.ac
十分感谢

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。