拓扑排序。
深刻体会:ACM比赛的精髓之处不在于学了某个算法或数据结构,而在于知道这个知识点但不知道这个问题可以用这个知识去解决!一看题目,根本想不到是拓扑排序。T_T......
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
int mapp[][]; char s[];
int i, j, k, f;
vector<int> abc[];
int jz[][];
int c[];
int ff[][];
void chushihua()
{
jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ; jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ; jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ; jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ; jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ; jz[][] = ;
jz[][] = ;
}
int main()
{
memset(jz, , sizeof(jz));
chushihua();int ge;
while (~scanf("%s", s))
{
for (i = ; i < ; i++)abc[i].clear();
memset(ff, , sizeof(ff));
if (strcmp("ENDOFINPUT", s) == ) break;
memset(c, , sizeof(c));
for (i = ; i <= ; i++) for (j = ; j <= ; j++) scanf("%d", &mapp[i][j]);
for (i = ; i <= ; i++)
{
for (j = ; j <= ; j++)
{
ge = (i - ) * + j;
for (f = ; f <= ; f++)
{
if (jz[ge][f] == && f != mapp[i][j])
{
if (ff[mapp[i][j]][f] == )
{
ff[mapp[i][j]][f] = ;
abc[mapp[i][j]].push_back(f);
c[f]++;
}
}
}
}
}
scanf("%s", s); int df, summ = ;
while ()
{
df = ;
for (i = ; i <= ; i++)
{
if (c[i] == )
{
c[i]--;df = ;summ++;
for (j = ; j < abc[i].size(); j++) c[abc[i][j]]--;
break;
}
}
if (summ == ){printf("THESE WINDOWS ARE CLEAN\n");break;}
if (df == ){printf("THESE WINDOWS ARE BROKEN\n");break;}
}
}
return ;
}