# Window Pains（图的应用）

• 转化为图，判断有没有环
• 暴力算法不好用，应该是输入数据不完全符合题意，用这种方法最保险了
``````#include iostream
#include cstring
#include algorithm
using namespace std;

char buf[100];
int a[10][10];
int io[10] = {0, 0, 0, 0, 1, 1, 1, 2, 2, 2};
int jo[10] = {0, 0, 1, 2, 0, 1, 2, 0, 1, 2};
bool G[10][10];
int vis[10];

void init()
{
memset(G, 0, sizeof(G));
memset(vis, 0, sizeof(vis));
}

// return 1 if having loop, 0 otherwise
bool dfs(int cur)
{
vis[cur] = 1;
for (int j = 1; j = 9; ++j)
if (G[cur][j]) {
if (vis[j] == 1)
return 1;
else if (vis[j] == 0)
if (dfs(j))
return 1;
}
vis[cur] = 2;
return 0;
}

bool judge()
{
for (int k = 1; k = 9; ++k) {
for (int i = io[k]; i  io[k]+2; ++i) {
for (int j = jo[k]; j  jo[k]+2; ++j) {
int m = a[i][j];
if (m != k)
G[m][k] = 1; // m covers k
}
}
}
for (int k = 1; k = 9; ++k) {
if (!vis[k])
if (dfs(k))
return 0;
}
return 1;
}

int main()
{
while (cin.getline(buf, 50)) {
init();
if (strcmp(buf, "ENDOFINPUT") == 0)
break;
for (int i = 0; i  4; ++i)
for (int j = 0; j  4; ++j)
scanf("%d", a[i][j]);
bool ans = judge();
if (ans)
printf("THESE WINDOWS ARE CLEAN\n");
else
printf("THESE WINDOWS ARE BROKEN\n");
getchar();
cin.getline(buf, 50);
}
system("pause");
return 0;
}
``````
• CS:GO