首页 > 代码库 > poj 1021
poj 1021
图同构。一个神奇的算法居然0ms过。真是不科学。反例可以构造出来。还是没有针对他的数据。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;struct position{ int x,y; }pos[10010];int w,h,n,map[105][105],sum[2][10010];int main(){ int T; cin>>T; while (T--){ cin >> w >> h >> n; memset(map,0,sizeof map); for (int i = 1;i <= n;i ++) { cin >> pos[i].x >> pos[i].y; map[pos[i].x][pos[i].y] = 1; } for (int i = 1;i <= n;i ++){ int xx = pos[i].x,yy = pos[i].y,x,y,cnt = 0; for (x = xx,y = yy;map[x][y] && y < h;++y,++cnt); for (x = xx,y = yy;map[x][y] && x < w;++x,++cnt); for (x = xx,y = yy;map[x][y] && y >= 0;--y,++cnt); for (x = xx,y = yy;map[x][y] && x >= 0;--x,++cnt); sum[0][i] = cnt; } memset(map,0,sizeof map); for (int i = 1;i <= n;i ++) { cin >> pos[i].x >> pos[i].y; map[pos[i].x][pos[i].y] = 1; } for (int i = 1;i <= n;i ++){ int xx = pos[i].x,yy = pos[i].y,x,y,cnt = 0; for (x = xx,y = yy;map[x][y] && y < h;++y,++cnt); for (x = xx,y = yy;map[x][y] && x < w;++x,++cnt); for (x = xx,y = yy;map[x][y] && y >= 0;--y,++cnt); for (x = xx,y = yy;map[x][y] && x >= 0;--x,++cnt); sum[1][i] = cnt; } sort(sum[0] + 1,sum[0] + 1 + n); sort(sum[1] + 1,sum[1] + 1 + n); int pd = 1; for (int i = 1;i <= n;i ++) if (sum[0][i] != sum[1][i]) { pd = 0;break; } if (!pd) puts("NO"); else puts("YES"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。