正方形划分"/>
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;
}
更多推荐
HDU 2589正方形划分
发布评论