POJ 1021 人品题
2024-08-31 06:57:20
报告见代码。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX=;
int dir[][]={,,-,,,,,-};
int h,w,n;
int maze[MAX][MAX];
int maze2[MAX][MAX];
struct{
int x,y;
}save[];
int sa;
int h1[];
int h2[]; void dfs(int i,int j,int (*p)[MAX]){
p[i][j]=;
save[++sa].x=i;save[sa].y=j;
for(int k=;k<;k++){
int tx,ty;
tx=i+dir[k][];
ty=j+dir[k][];
if(p[tx][ty]==&&tx<h&&tx>=&&ty<w&&ty>=)
dfs(tx,ty,p);
}
} void calculate(int *ha,int &top){ //HASH函数是各点对的距离的平方。。。也过。
int i,j,x=,y=; top++;
for(i=;i<=sa;i++){
x=save[i].x;
y=save[i].y;
for(j=i+;j<=sa;j++){
int dx=abs(x-save[j].x);
int dy=abs(y-save[j].y);
int dis=dx*dx+dy*dy;
ha[top]+=dis;
}
}
} void slove(int (*p)[MAX],int *ha,int &top){
int i,j;
for(i=;i<h;i++){
for(j=;j<w;j++){
sa=;
if(p[i][j]==){
dfs(i,j,p);
calculate(ha,top);
}
}
}
} int main(){
int x,y,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&w,&h,&n);
memset(maze,,sizeof(maze));
memset(maze2,,sizeof(maze2));
memset(h1,,sizeof(h1));
memset(h2,,sizeof(h2));
int top1=-,top2=-;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
maze[y][x]=;
}
/* for(int i=0;i<h;i++){
for(int j=0;j<w;j++)
printf("%d ",maze[i][j]);
printf("\n");
}*/
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
maze2[y][x]=;
}
/* for(int i=0;i<h;i++){
for(int j=0;j<w;j++)
printf("%d ",maze2[i][j]);
printf("\n");
}*/
slove(maze,h1,top1);
slove(maze2,h2,top2);
if(top1!=top2){
printf("NO\n");
continue;
}
bool flag=true;
sort(h1,h1+top1+);
sort(h2,h2+top2+);
for(int i=;i<=top1;i++){
// printf("%d %d \n",h1[i],h2[i]);
if(h1[i]!=h2[i]){
flag=false;
break;
}
}
if(!flag)
printf("NO\n");
else
printf("YES\n");
}
return ;
}
最新文章
- JQ的表单验证
- SSDB 主从配置
- FeWeb基础之HTML
- Spark学习(二) -- Spark整体框架
- Python 3.x自定义迭代器对象
- mysql JDBC URL格式
- VMware中第一次启动mac遇到的错误及解决方案
- android利用反射通过代码收缩通知栏
- 树莓派编译C++
- 阿里巴巴Java开发手册评
- bzoj 4545: DQS的trie
- Spring-----AOP-----事务
- java List集合
- Intellj(IDEA)创建java webapp
- QT creator 编辑器快捷键
- DbHelper.ttinclude 更新,查询视图和表
- Emgucv(一)Aforge切换摄像头并调用摄像头属性
- STL - Map - 运行期自定义排序
- laravel的模型和数据库基础操作
- HDU1005 Number Sequence(找规律,周期是变化的)
热门文章
- 手写DAO框架(一)-从“1”开始
- .Net Core中使用Quartz.Net Vue开即用的UI管理
- [JZOJ3809]设备塔
- POJ1915 BFS&;双向BFS
- 【Oracle】闪回表
- C# 彻底关闭程序,包括循环
- MSP430之software development flow
- OpenCV:OpenCV目标检测Boost方法训练
- 极客学院免费VIP
- eclipse中导入maven项目:org.apache.maven.archiver.MavenArchiver.getManifest(org.apache.maven.proje