首页 > 代码库 > bzoj4423 [AMPPZ2013]Bytehattan
bzoj4423 [AMPPZ2013]Bytehattan
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4423
【题解】
转对偶图,格子当成点,就相当于并查集裸题了。。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3e6 + 10, N = 1510; const int mod = 1e9+7; # define RG register # define ST static int n, q, out, idx; int id[N][N], fa[M]; inline int getf(int x) { return fa[x] == x ? x : fa[x] = getf(fa[x]); } int main() { cin >> n >> q; for (int i=1; i<=n-1; ++i) for (int j=1; j<=n-1; ++j) id[i][j] = ++idx; out = ++idx; for (int i=1; i<=idx; ++i) fa[i] = i; bool o = 0; int x, y, u, v, fu, fv; char opt[5]; while(q--) { if(o) scanf("%*d%*d%*s%d%d%s", &x, &y, opt); else scanf("%d%d%s%*d%*d%*s", &x, &y, opt); if(opt[0] == ‘N‘) { // (x,y)->(x,y+1) if(x == 1) u = out; else u = id[x-1][y]; if(x == n) v = out; else v = id[x][y]; } if(opt[0] == ‘E‘) { // (x,y)->(x+1,y) if(y == 1) u = out; else u = id[x][y-1]; if(y == n) v = out; else v = id[x][y]; } // cout << u << ‘ ‘ << v << endl; fu = getf(u); fv = getf(v); if(fu == fv) o = 1; else o = 0; if(fu != fv) fa[fu] = fv; puts(o ? "NIE" : "TAK"); } return 0; }
bzoj4423 [AMPPZ2013]Bytehattan
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。