一道很水的topsort,唉？怎么交了14遍…（某人用我的代码刚好卡过，我怎么过不去…【鄙视】【鄙视】【鄙视】）
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f
#define MAXN 1000010
#define MAXM 5010int n,m,len = ,tot = ,lin[MAXN],top = ,a[],vis[],in[];
char ch[][];
string st[MAXN],s1;
struct node
{
int ix,iy;
int ax,ay;
}q[];
struct edge
{
int y,next;
}e[MAXN];inline void add(int xx,int yy)
{
e[++tot].y = yy;
e[tot].next = lin[xx];
lin[xx] = tot;
}void DFS(string xx,int le)
{
if(le == len + )
{
st[++top] = xx;
return ;
}
for(int k = ;k <= len;++k)
{
int i = a[k];
if(vis[i] && in[i] == )
{
vis[i] = false;
for(int j = lin[i],y;j;j = e[j].next)
in[y = e[j].y]--;
DFS((xx + (char)(i + 'A' - )),le + );
vis[i] = true;
for(int j = lin[i],y;j;j = e[j].next)
in[y = e[j].y]++;
}
}
}namespace ls {
inline int kmax(int a, int b) { return a > b ? a : b; }
inline int kmin(int a, int b) { return a > b ? b : a; }
}int main()
{
scanf("%d %d", &n, &m);
for(int i = ;i <= ;++i)
q[i].ix = INF,q[i].iy = INF;
for(int i = ;i <= n;++i)
{
for(int j = ;j <= m;++j)
{
cin >> ch[i][j];
if(ch[i][j] == '.') continue;
int num = (int)ch[i][j] - 'A' + ;
if(!vis[num])
{
vis[num] = true;
a[++len] = num;
}
q[num].ix = ls::kmin(i,q[num].ix);
q[num].iy = ls::kmin(j,q[num].iy);
q[num].ax = ls::kmax(i,q[num].ax);
q[num].ay = ls::kmax(j,q[num].ay);
}
}
for(int ii = ;ii <= len;++ii)
{
int num = a[ii];
char c = (char)(num + 'A' - );
for(int i = q[num].ix;i <= q[num].ax;++i)
{
if(ch[i][q[num].iy] != c)
{
int numm = ch[i][q[num].iy] - 'A' + ;
in[numm]++;
add(num,numm);
}
if(ch[i][q[num].ay] != c)
{
int numm = ch[i][q[num].ay] - 'A' + ;
in[numm]++;
add(num,numm);
}
}
for(int i = q[num].iy + ;i <= q[num].ay - ;++i)
{ if(ch[q[num].ix][i] != c)
{
int numm = ch[q[num].ix][i] - 'A' + ;
in[numm]++;
add(num,numm);
}
if(ch[q[num].ax][i] != c)
{
int numm = ch[q[num].ax][i] - 'A' + ;
in[numm]++;
add(num,numm);
}
}
}
DFS(s1,);
sort(st + ,st + top + );
for(int i = ;i <= top;++i)
cout << st[i] << endl;
return ;
}
以下代码会很快↓↓↓
#include <bits/stdc++.h>
#define INF ((int)(1e9))
#define LINF ((ll)(1e18))
#define pb push_back
#define mp make_pair
#define ll long long
#define _tp template
#define _tyn typename
#define ull unsigned ll
#define pii pair<int,int>
#define uint unsigned int
#define ms(_data) memset(_data,0,sizeof(_data))
#define fin(_filename) freopen(_filename,"r",stdin)
#define fout(_filename) freopen(_filename,"w",stdout)
#define msn(_data,_num) memset(_data,_num,sizeof(_data))
using namespace std;
_tp<_tyn T>void mymax( T &_a , T _b ){ if( _a < _b ) _a = _b; }
_tp<_tyn T>void mymin( T &_a , T _b ){ if( _a > _b ) _a = _b; }
int getnum(){
char ch = '.';
int fu = ;
while( ch < '' || ch > '' ){
ch = getchar();
if( ch == '-' ) fu = -;
}
int ret = ;
while( ch >= '' && ch <= '' ){
ret = ret * + (ch-'');
ch = getchar();
}
return ret;
}
char getlet(){
char ch = '%';
while( ( ch < 'A' || ch > 'Z' ) && ch != '.' ) ch = getchar();
return ch;
}
void read( int &x, int &y ){
x = getnum(); y = getnum();
}
void read( char &c ){
c = getlet();
}
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
#define MAXN 40
struct Pos{
int y,x;
Pos(){}
Pos( int yy , int xx ){
y = yy;
x = xx;
}
};
int n,m;
int data[MAXN][MAXN];
Pos ld[MAXN],ur[MAXN];
bool exist[MAXN];//检测一个矩形是否完整
bool test( int x ){
for( int i = ld[x].x ; i <= ur[x].x ; i++ ){
if( data[ld[x].y][i] != x && data[ld[x].y][i] != - ) return ;
if( data[ur[x].y][i] != x && data[ur[x].y][i] != - ) return ;
}
for( int i = ur[x].y ; i <= ld[x].y ; i++ ){
if( data[i][ld[x].x] != x && data[i][ld[x].x] != - ) return ;
if( data[i][ur[x].x] != x && data[i][ur[x].x] != - ) return ;
}
return ;
}
//消除一个矩形
void seton( int x , int a ){
for( int i = ld[x].x ; i <= ur[x].x ; i++ ){
data[ld[x].y][i] = a;
data[ur[x].y][i] = a;
}
for( int i = ur[x].y ; i <= ld[x].y ; i++ ){
data[i][ld[x].x] = a;
data[i][ur[x].x] = a;
}
}vector<string> ans;
void dfs( string now ){
bool gao = ;
for( int i = ; i < ; i++ ){
if( !exist[i] ) continue;
if( !test(i) ) continue;
gao = ;
exist[i] = ;
int ls[MAXN][MAXN];
memcpy(ls,data,sizeof(ls));
seton(i,-);
dfs( now + (char)(i+'A') );
memcpy(data,ls,sizeof(data));
exist[i] = ;
}
if( gao ) return;
reverse(now.begin(),now.end());
ans.pb(now);
}
int main(){
//fin("frameup.in");
//fout("frameup.out");
for( int i = ; i < ; i++ ){
ld[i].y = ; ld[i].x = INF;
ur[i].y = INF; ur[i].x = ;
}
msn(data,-);
ms(exist); read(n,m);
for( int i = ; i <= n ; i++ ){
for( int j = ; j <= m ; j++ ){
char c; read(c);
if( c == '.' ) continue;
data[i][j] = c-'A';
exist[data[i][j]] = ;
//记录矩形左下角、右上角坐标
mymax( ld[data[i][j]].y , i );
mymin( ld[data[i][j]].x , j );
mymin( ur[data[i][j]].y , i );
mymax( ur[data[i][j]].x , j );
}
}
dfs("");
//整理答案
sort(ans.begin(),ans.end());
for( uint i = ; i < ans.size() ; i++ )
cout << ans[i] << endl; return ;
}
