问题描述
李教授将于今天下午作一次非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n≤26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编了号。因为幻灯片是透明的，所以我们用大写字母A，B，C，…再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若是出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们就称对应是无法实现的。
输入文件（slides.in）
文件的第1行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，…，再接下来的n行依次为n个数字编号的坐标x，y，显然在幻灯片之外是不会有数字的。
输出文件（slides.out）
若是对应可以实现，则输出文件包括n行，每一行一个字母和一个数字，中间一个空格，各行以字母的升序排列；若是对应无法实现，在文件的第一行顶格输出None即可。
样例输入
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
样例输出
A 4
B 1
C 2
D 3
#include<iostream>
#include<vector>
using namespace std;
int xmin[100],xmax[100],ymin[100],ymax[100];//记录每个幻灯片的坐标
int xx[100],yy[100];//记录每个数字的坐标
int pd[100];//第i个数字被pd[i]个幻灯片指向
int ans[100];//第i个幻灯片指向第ans[i]个幻灯片
int n;//n个幻灯片和n个数字
vector<int> map[100];//向量容器建图
int main(){
cin>>n;
for(int i=1;i<=n;i++) pd[i]=0;//初始化pd数组
for(int i=1;i<=n;i++)
cin>>xmin[i]>>xmax[i]>>ymin[i]>>ymax[i];//输入每个幻灯片的坐标
for(int i=1;i<=n;i++)
cin>>xx[i]>>yy[i];//输入每个数字的坐标
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(xmin[i]<=xx[j]&&xmax[i]>=xx[j]&&ymin[i]<=yy[j]&&ymax[i]>=yy[j]){
map[i].push_back(j);//如果第j个字母在第i个幻灯片内，则i->j
pd[j]++;//记录第i个数字被几个幻灯片指向
}
bool t=true;//t=true表示有解
int tot=0;//表示已有tot个幻灯片被确认对应数字
while(t==true||tot<n){
t=false;//如果无法进一步确认，则t返回到while的值为true
for(int i=1;i<=n;i++)
if(pd[i]==1){//找被唯一幻灯片指向的数字
for(int x=1;x<=n;x++)
for(int y=0;y<map[x].size();y++){
if(map[x][y]==i){//x为所求的幻灯片的标号
for(int j=0;j<map[x].size();j++)
pd[map[x][j]]--;//x指向的所有数字的被指向数-1
map[x].clear();//相当于删除x这个点
t=true;//当前循环中进一步确认了一个幻灯片的数字
tot++;//又有一个幻灯片被确认
ans[x]=i;//x幻灯片->i数字
}
}
}
}
if(tot!=n) cout<<"None"<<endl;
else
for(int i=1;i<=n;i++){
char ch;
ch=i+64;
cout<<ch<<" "<<ans[i]<<endl;
}//输出
return 0;
}
