根据题意,每个矩形总能找到他的四个角的坐标,先找出各个矩形,再遍历每个矩形的四条边,例如:若在遍历矩形A的四条边时候,遇到B。
则图中存在边A->B
如此建立边的关系之后即刻拓扑排序。最后对结果进行排序。
PS:结果数量比较大。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: frameup
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <cstring>
#include <algorithm>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXL = 30;
const int MAXA = 10000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Rect
{
char letter;
int xmin, xmax, ymin, ymax;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Sequeue
{
char strs[MAXL];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool operator < (const Sequeue &seq)const
{
int re = strcmp(strs, seq.strs);
if(re<0)
return true;
else
return false;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("frameup.in");
ofstream fout("frameup.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Rect rect[MAXL];
Sequeue ans[MAXA];
int acnt, len;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char board[MAXL][MAXL];
bool map[MAXL][MAXL], visited[MAXL], used[MAXL];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m,l;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline int min(int a, int b)
{
return a<b? a:b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline int max(int a, int b)
{
return a>b? a: b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i,j,k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>n>>m;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<n; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<m; ++j)
{
char ch;
fin>>ch;
board[i][j]=ch;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(ch=='.')
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
k = ch-'A';
if(k>len) len=k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!used[k])
{
l++;
used[k]=true;
rect[k].letter=ch;
rect[k].xmax = i, rect[k].xmin = i, rect[k].ymax = j, rect[k].ymin = j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
rect[k].xmax = max(rect[k].xmax, i);
rect[k].xmin = min(rect[k].xmin, i);
rect[k].ymax = max(rect[k].ymax, j);
rect[k].ymin = min(rect[k].ymin, j);
}
}
fin.get();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=0; k<MAXL; ++k)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(used[k])
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int x=rect[k].xmin, y1=rect[k].ymin, y2=rect[k].ymax; x<=rect[k].xmax; ++x)
{
int p1 = board[x][y1] - 'A';
if(k!=p1)
map[k][p1]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int p2 = board[x][y2] - 'A';
if(k!=p2)
map[k][p2]=true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int y=rect[k].ymin, x1=rect[k].xmin, x2=rect[k].xmax; y<=rect[k].ymax; ++y)
{
int p1 = board[x1][y] - 'A';
if(k!=p1)
map[k][p1]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int p2 = board[x2][y] - 'A';
if(k!=p2)
map[k][p2]=true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char tmp[30];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool hasprefix(int u)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<=len; ++i)
{
if(!used[i]) continue;
if(map[i][u] && !visited[i])
return true;
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void topsort(int u, int k)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k==l)
{
strcpy(ans[acnt++].strs, tmp);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
visited[u]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<=len; ++i)
{
if(!used[i])
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!visited[i] && !hasprefix(i))
{
tmp[k]=rect[i].letter;
topsort(i, k+1);
}
}
visited[u]=false;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void solve()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<=len; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(used[i] && !hasprefix(i))
{
tmp[0] = rect[i].letter;
topsort(i, 1);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
sort(ans, ans+acnt);
for(int i=0; i<acnt; ++i)
fout<<ans[i].strs<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
solve();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted on 2011-02-04 16:48
小阮 阅读(349)
评论(0) 编辑 收藏 引用 所属分类:
USACO