Window Pains(图的应用)

题目链接: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;
}
最新回复(0)
/jishuJL0LpEFuOWOS0URwbo2fGmymnF3fdwcx31x_2BuA_3D_3D4794676
8 简首页