练习1 - 烦人的幻灯片

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<sstream>
using namespace std;
#define L 101
#define MAX 0x3f
int n;
int a[L][4],x,y;	
int g1[L][L],g2[L][L];	//数字+字母 
int n1[L],n2[L];	//记录len 
int f[L];	//储存结果 字母=>数字 
int sum=0,bt,t;
bool flag=true; 

void delPoint(int k,bool mode){	//mode:1 =>数字 0:字母 
	if(mode){	//数字 
		bt=0;	//看是否有多个重复对应 
		for(int i=1;i<=n;i++){
			if(g1[k][i]){
				g1[k][i]=0;	//双向断线 
				g2[i][k]=0;
				bt++;
				t=i;
				f[t]=k;	//记录结果
				//cout << "字母"<<i<<endl; 
			}
		}
		if(bt!=1){cout << "None";flag=false;return;}	//无解/多解 
		else{
			//将对应字母的其他所有线都删除
			n2[t]=0;	//清空字母的len 
			for(int i=1;i<=n;i++){
			 	if(g2[t][i]){
			 		g2[t][i]=0;	//断线
			 		g1[i][t]=0;
					n1[i]--;	//对应的数字少1条线 
				}
			 }
		}
	}
	//—————————————————————————————— 
	else{	//字母 
		bt=0;	//看是否有多个重复对应 
		for(int i=1;i<=n;i++){
			if(g2[k][i]){
				g2[k][i]=0;	//断线
				g1[i][k]=0;
				bt++;
				t = i;
				f[k]=t;	//记录结果 
				//cout << "数字"<<i<<endl; 
			}
		}
		if(bt!=1){cout << "None";flag=false;return;}	//无解/多解 
		else{
			//将对应数字的其他所有线都删除
			n1[t]=0;	//清空数字的len 
			for(int i=1;i<=n;i++){
			 	if(g1[t][i]){
			 		g1[t][i]=0;	//断线
			 		g2[i][t]=0;
					n2[i]--;	//对应的字母少1条线 
				}
			 }
		}
	}
}

int main()
{
	//1.读取ppt坐标 
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	}
	//2.读取数字坐标
	for(int i=1;i<=n;i++){
		cin >> x >> y;
		for(int j=1;j<=n;j++){
			if(x>=a[j][0] && x<=a[j][1] && y>=a[j][2] && y<=a[j][3]){	//符合PPT 
				g1[i][j]=1;	//数字=>字母 
				n1[i]++;
				g2[j][i]=1;
				n2[j]++;
			} 
		}
	}
	//3.拓扑排序思想
	while(sum<n && flag){
		for(int i=1;i<=n;i++){	//检查数字为1？ 
			if(n1[i]==1){
				//cout << "数字"<<i;
				n1[i]--;	
				delPoint(i,1);
				sum++;	//多一个匹配好的 
			}
			if(!flag)break;	//及时退出 
		}
		for(int i=1;i<=n;i++){	//检查字母为1？ 
			if(n2[i]==1){
				//cout << "字母"<<i; 
				n2[i]--;	
				delPoint(i,0);
				sum++;	//多一个匹配好的 
			}
			if(!flag)break;	//及时退出 
		}
	}
	for(int i=1;i<=n;i++){
		cout <<char(i+'A'-1)<<" "<<f[i]<<endl;
	}
	return 0;
}
/*
4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11
*/
//cout << "输入："

结果：