HDU 2589正方形划分

正方形划分"/>

HDU 2589正方形划分

正方形划分

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 235    Accepted Submission(s): 132


Problem Description 一个边长为L的正方形可以分成 L*L个小正方形. 有N个石子放在 N个小正方形里，能否将它分成 N个 正方形，使得每个正方形里恰有一个石子且这N 个正方形恰好构成整个正方形 .
Input 输入数据首先包含一个整数T，表示测试实例的个数，然后是T组数据，每组第一行包含2个整数L,N,接下来有N行每行2个整数 r,c,表示第r行c列的小正方形里有一个石子 .1<L<=20;1<N<=L*L; 1<=r,c<=L.
Output 对于每个测试实例，如能将它分成 N个 正方形输出YES, 否则输出 NO
Sample Input

  35 8
2 4
3 3
3 4
3 5
4 2
4 4
4 5
5 53 2
1 1
3 32 4
1 1
1 2
2 1
2 2

Sample Output

  YES
NO
YES

Source ECJTU 2009 Spring Contest
Recommend

lcy   |   We have carefully selected several similar problems for you:  2580 2583 2587 2585 2584

此题关键在于如何找到结题的突破口，初次做题由于dfs这一块了解的并不是非常深入，可能会有一些思路可要动手用代码实现便瞬间卡壳了！

没办法参考网上大牛代码后才总算将此题的代码敲出来。总得来说还是题目接触太少，不懂得变通——————码农的辛酸....

思路：定义三个数组分别用来存放初始的键入矩阵map，然后在map的基础上利用num[i][j]数组来存放从（1,1）到(i,j)范围内有多少颗石子。用vis

数组来记录被覆盖的位置随后遍历...具体实现请参考代码与注释：

/*#include<iostream>
#include<cstring>
using namespace std;
int map[21][21],vis[21][21],num[21][21];
int l,r,n,c;
int dfs(){int i,j,x,y,flag=1;for(i=1;i<=l;i++){  //找到未分割正方形的位置坐标if(!flag)break;for(j=1;j<=l;j++){if(!vis[i][j]){x=i;y=j;flag=0;break;}}}int k=0;while(x+k<=l&&y+k<=l){int x1=x+k;int y1=y+k;int count=num[x1][y1]-num[x1][y-1]-num[x-1][y1]+num[x-1][y-1];//计算当前正方形内点的数目if(count>1)//大于1不符合break;else if(count==1){for(i=x;i<=x1;i++) //填充该正方形for(j=y;j<=y1;j++)vis[i][j]=1;if(dfs()) //继续填充，满足所求条件返回1.return 1;for(i=x;i<=x1;i++)for(j=y;j<=y1;j++)vis[i][j]=0; //回溯到未填充该正方形的状态}k++;}for(i=1;i<=l;i++) //判断是否满足所求条件for(j=1;j<=l;j++)if(!vis[i][j])return 0;return 1;
}
int main(){int T;cin>>T;while(T--){memset(num,0,sizeof(num));memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));cin>>l>>n;for(int i=1;i<=n;i++){cin>>r>>c;map[r][c]=1;}for(int i=1;i<=l;i++)for(int j=1;j<=l;j++)num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+map[i][j];//统计从(1，1)到(i，j)的矩形中有多少个小石子  num[i-1][j-1]多加一次因此需要减去一次if(dfs())cout<<"YES"<<endl;elsecout<<"NO"<<endl; }return 0;
} */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[21][21];
int num[21][21];
bool vis[21][21];
int n,m;
bool dfs()
{int i,j;int x,y,r;int flag=0;for(i=1;i<=n;i++) //找到未被分割正方形的位置坐标 {if(flag) break;for(j=1;j<=n;j++)if(!vis[i][j]){x=i;y=j;  //记录其下标位置，起始位置必然是从（1,1）开始 flag=1;break;}}int x1,y1;/*每次找到没有覆盖的区域，记录坐标(x，y)，开始遍历小正方形的边长，直到找到刚好包含1个小石子的正方形区域，将其覆盖，然后接着深搜找到没有覆盖的区域……如果没有找到刚好包含1个小石子的正方形区域，将其回溯到没有覆盖的状态继续深搜。如果所有区域都能被覆盖，则说明满足条件，返回1。代码实现如下： 
*/ for(r=0;;r++){x1=x+r;y1=y+r;if(x1>n||y1>n) break; //如果遍历超界，自然要退出 if(num[x1][y1]-num[x1][y-1]-num[x-1][y1]+num[x-1][y-1]>1) break; //如果在该范围内包含两个石头自然也要退出 if(num[x1][y1]-num[x1][y-1]-num[x-1][y1]+num[x-1][y-1]==1) //满足条件 {for(i=x;i<=x1;i++)for(j=y;j<=y1;j++) //填充该方阵 vis[i][j]=1;if(dfs()) return 1; //继续遍历 for(i=x;i<=x1;i++) //回溯到为填充之前的状态 for(j=y;j<=y1;j++)vis[i][j]=0;}}for(i=1;i<=n;i++) //判断是否满足所有条件 for(j=1;j<=n;j++)if(!vis[i][j])return 0;return 1;
}
int main()
{int cas,x,y;scanf("%d",&cas);while(cas--){memset(map,0,sizeof(map));scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&x,&y);map[x][y]=1;}memset(num,0,sizeof(num));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+map[i][j];memset(vis,0,sizeof(vis));if(dfs())printf("YES\n");else printf("NO\n");}return 0;
}