[pat1139]First Contact 前导零

First Contact

题意

给定一个图，图中的点只有男的点或者女的点。给定两个不同的点AB，问他们第一个点通过两个不同的点找到第二个点，并且A找到的点和A同性，B连接的点跟B同性，这样的点对有多少对。

题解

暴力枚举即可，找到所有相邻的同性点，之后同性点之间有连接就是一对点对。

• wa点 前导零输出，-0000输入
• 中间的点不能是两边的点，必须是不同的四个点

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
map<int,int> mx;
const int maxn = 3e2+10;
int vis[maxn][maxn];
int idx[maxn];
int gender[maxn];
void output(int x){
    char ch[10];
    ch[0] = '0';
    ch[1] = '0';
    ch[2] = '0';
    ch[3] = '0';
    ch[4] = '\0';
    int cnt = 3;
    while(x){
        ch[cnt--] = (x%10)+'0';
        x /= 10;
    }
    printf("%s",ch);
}
int trans(string x,int &sign){
    int a = 0;
    int sz = x.size();
    if(x[0] == '-'){
        rep(i,1,sz){
            a += pow(10,4-i) * (x[i] - '0');
        }
        sign = 1;
    }else{
        rep(i,0,sz){
            a += pow(10,3-i) * (x[i] - '0');
        }
    }
    return a;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt = 1;
    rep(i,0,m){
        string a,b; cin>>a>>b;
        int x,y; 
        int sign1 = 0,sign2 = 0;
        x = trans(a,sign1) ; y = trans(b,sign2);
        if(mx[x] == 0){
            mx[x] = cnt++;
            if(sign1) gender[mx[x]] = 1;
            idx[mx[x]] = x;
        }
        if(mx[y] == 0){
            mx[y] = cnt++;
            if(sign2) gender[mx[y]] = 1;
            idx[mx[y]] = y;
        }
        int id1 = mx[x];
        int id2 = mx[y];
        vis[id1][id2] = vis[id2][id1] = 1;
    }
    int k;scanf("%d",&k);
    rep(i,0,k){
        int x,y; scanf("%d%d",&x,&y);
        x = max(-1*x,x);
        y = max(-1*y,y);
        int id1 = mx[x]; int id2 = mx[y];
        vector<int> xx;vector<int> yy;
        if(id1 == 0 || id2 == 0){
            puts("0");
            continue;
        }
        rep(j,1,cnt+1) 
            if(j != id2 && vis[id1][j] && (gender[id1]^gender[j]) == 0)
                xx.push_back(j);
        rep(j,1,cnt+1) 
            if(j != id1 && vis[id2][j] && (gender[id2]^gender[j]) == 0)
                yy.push_back(j);
        vector<pair<int,int>> ans;
        for(auto x:xx){
            for(auto y:yy){
                if(vis[x][y] == 1){
                    ans.push_back(make_pair(idx[x],idx[y]));
                }
            }
        }
        sort(ans.begin(),ans.end());
        printf("%d\n",ans.size());
        for(auto x:ans){
            output(x.fi); printf(" "); output(x.se);
            puts("");
            //printf("%d %d\n",x.fi,x.se);
        }
    }
    return 0;
}