ruiming / algorithm Goto Github PK

ZOJ2770 - Burn the Linked Camp

题目

It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision that he divided his large troops into a number of camps, each of which had a group of armies, and located them in a line. This was the so-called "Linked Camps".

Let's go back to that time. Lu Xun had sent many scouts to obtain the information about his enemy. From his scouts, he knew that Liu Bei had divided his troops into n camps, all of which located in a line, labeled by 1..n from left to right. The ith camp had a maximum capacity of Ci soldiers. Furthermore, by observing the activities Liu Bei's troops had been doing those days, Lu Xun could estimate the least total number of soldiers that were lived in from the ith to the jth camp. Finally, Lu Xun must estimate at least how many soldiers did Liu Bei had, so that he could decide how many troops he should send to burn Liu Bei's Linked Camps.

Input:

There are multiple test cases! On the first line of each test case, there are two integers n (0<n<=1,000) and m (0<=m<=10,000). On the second line, there are n integers C1��Cn. Then m lines follow, each line has three integers i, j, k (0<i<=j<=n, 0<=k<2^31), meaning that the total number of soldiers from the ith camp to the jth camp is at least k.

Output:

For each test case, output one integer in a single line: the least number of all soldiers in Liu Bei's army from Lu Xun's observation. However, Lu Xun's estimations given in the input data may be very unprecise. If his estimations cannot be true, output "Bad Estimations" in a single line instead.

Sample Input:

3 2
1000 2000 1000
1 2 1100
2 3 1300
3 1
100 200 300
2 3 600

Sample Output:

1300
Bad Estimations

知识点

差分约束系统，Bellman-ford, SPFA

分析

这道题的意思是刘备的军队分为了n个阵营，每个阵营的最大士兵容量为Ci。陆逊通过观察发现得出了几组数据，就是从阵营from到阵营to之间的士兵最少数量。陆逊这时候必须估计刘备有多少士兵，如果无法估计，输出Bad Estimations。

此题应该使用差分约束系统来解决。

求解差分约束系统，可以转化成图论的单源最短路径问题。观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每个变数xi为结点，对于约束条件xj-xi<=bk，连接一条边（i,j），边权为bk。再增加一个原点（s,s）与所有定点相连，边权均为0。对这个图以s为原点运行Bellman-ford算法（或SPFA算法），最终{d[i]}即为一组可行解。

解决这道题要首先找出差分方程组，对这道题来说，我们可以建立以下约束方程

根据军营数和每个军营的最大士兵容量Ci可以得到:

• ( i - 1 ) - ( i ) <=0 // 前i-1个军营的士兵与前i个军营的士兵之差必然小于等于0
• ( i ) - ( i - 1 ) <= temp // 前i个军营的士兵数量减去前i-1个军营的士兵数量必然小于等于Ci

根据第from到to个军营之间最少有number个士兵可以得到:

• ( to ) - ( from - 1 ) >= number

我们需要统一差分方程，上述可以转化为:

• ( from - 1 ) - ( to ) <= -number

保存上述的全部差分方程，接着我们要计算的是刘备至少有多少士兵。即

• ( n ) - ( 0 ) >= ? 即 ( 0 ) - ( n ) <= -?

如果从数学角度，其实就是我们有这么多个不等式，问能不能求出( 0 ) - ( n )的最大值？

从程序角度，我们已经找到了多个类似从A点到B点的权值大小这样的关系。要求的是起始点到终点的最小权值即最短路径。但会出现权值为负数的情况，对于带负数权值的求最短路径的问题，可以使用Belleman-ford算法。

Bellman-ford算法有三个步骤

• 初始化图
• 重复对每一条边进行松弛操作
• 检查负权环

我们由此题可以建立(u, v, w)的图（数组表示）如下：

一共有n个点，所以我们要进行n次循坏，每次循坏都对这8个关系进行遍历。初始d[n] = 0，表示第n个军营到第n个军营最小权值为0。可见我们要求的是( 0 ) - ( n )，即 d[0] 。最后我们还要求反。

如上，最后得到d[0] = -1300，所以结果为1300。

第i次循环表示走i次到达n点的最小权值。

程序

// 差分约束系统 转为 Bellmanford（SPFA）, 判断负环
#include <iostream>
#include <cstring>
using namespace std;
#define maxn 1005

struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int uu, int vv, int ww) :u(uu), v(vv), w(ww) {}
}e[maxn*maxn];

int sd[maxn];	// 前i个兵营中的最大士兵
int d[maxn];
int n, m, l;

bool bellmanford(int x)
{
    memset(d, 999999, sizeof(d));
    d[x] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) {
            int u = e[j].u, v = e[j].v, w = e[j].w;
            if (d[v] > d[u] + w)
                d[v] = d[u] + w;
        }
    }
    // 负环判断
    for (int i = 0; i < l; i++)
        if (d[e[i].v] > d[e[i].u] + e[i].w)
            return false;
    return true;
}

int main() {
    while (cin >> n >> m) {					// 军营数n
        int a, b, c, number;
        memset(sd, 0, sizeof(sd));
        l = 0;
        for (int i = 1; i <= n; i++) {
            cin >> number;
            e[l++] = Edge(i, i - 1, 0);			// (i-1) - (i) <=0
            e[l++] = Edge(i - 1, i, number);		// (i) - (i-1) <= temp
        }
        for (int i = 1; i <= m; i++) {
            cin >> a >> b >> c;
            e[l++] = Edge(b, a-1, -c);			// b - (a-1) >=c -> (a-1) - b <= -c
        }
        // 计算(n) - (0) >= ? 即 (0) - (n) <= -?, 所以bellmanford(n)后输出-d[0]
        if (!bellmanford(n))	cout << "Bad Estimtions" << endl;
        else  cout << -d[0] << endl;
    }
    return 0;
}

ZOJ2734 - Exchange Cards

题目

As a basketball fan, Mike is also fond of collecting basketball player cards. But as a student, he can not always get the money to buy new cards, so sometimes he will exchange with his friends for cards he likes. Of course, different cards have different value, and Mike must use cards he owns to get the new one. For example, to get a card of value 10$, he can use two 5$ cards or three 3$ cards plus one 1$ card, depending on the kinds of cards he have and the number of each kind of card. And Sometimes he will involve unfortunately in a bad condition that he has not got the exact value of the card he is looking for (fans always exchange cards for equivalent value).

Here comes the problem, given the card value he plans to get and the cards he has, Mike wants to fix how many ways he can get it. So it's you task to write a program to figure it out.

Input

The problem consists of multiple test cases, terminated by EOF. There's a blank line between two inputs.

The first line of each test case gives n, the value of the card Mike plans to get and m, the number of different kinds of cards Mike has. n will be an integer number between 1 and 1000. m will be an integer number between 1 and 10.

The next m lines give the information of different kinds of cards Mike have. Each line contains two integers, val and num, representing the value of this kind of card, and the number of this kind of card Mike have.

Note: different kinds of cards will have different value, each val and num will be an integer greater than zero.

Output

For each test case, output in one line the number of different ways Mike could exchange for the card he wants. You can be sure that the output will fall into an integer value.

Output a blank line between two test cases.

Sample Input

5 2
2 1
3 1

10 5
10 2
7 2
5 3
2 2
1 5

Sample Output

1

7

分析

这道题目的意思是，以第二个例子为例，迈克想换去价值为10的卡片，他有5种卡片，他有价值为10的卡片2张，价值为7的卡片2张，价值为5的卡片3张，价值为2的卡片2张，价值为1的卡片5张。问他可以有多少种组合方式去换去价值为10的这张卡片。

其实意思就是找出可以有多少种加法组合得到要求的数字。

说到这里我们可以很明显想到这道题用深度遍历DFS来解决。分别考虑一次加法，二次加法，三次加法等等。

需要注意的是一定要按降序来进行深度遍历。

程序

#include <stdio.h>  
#include <iostream>  
#include <string.h>
using namespace std;
int num[1010];
int sum, result;
int wanted, line;
void DFS(int x) {
    if (sum == wanted) {
        result++;
        return;
    }
    for (int i = x; i <= wanted; i++) {
        if (num[i] && sum + i <= wanted) {
            num[i]--;
            sum += i;
            DFS(i);
            num[i]++;
            sum -= i;
        }
        else if (sum + i > wanted) {
            break;
        }
    }
}

int main() {
    int m, n;
    bool first = true;
    while (cin >> wanted >> line) {
        if (!first)	cout << endl;
        first = false;
        memset(num, 0, sizeof(num));
        sum = result = 0;
        for (int i = 0; i<line; i++) {
            cin >> m >> n;
            num[m] = n;
        }
        DFS(1);
        cout << result << endl;
    }
    return 0;
}

ZOJ1002 - Fire Net

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

Sample input:

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Sample output:

5
1
5
2
4

分析

这道题的意思很明显，在一张4X4的地图中放置碉堡，碉堡不能同行或同列，除非中间有墙阻隔。问最多能放置多少个碉堡。

做这道题的时候还不了解二分图，所以用的DFS方法。此题最佳解法应是使用二分图。

关于DFS的做法这里不再多说，以后再改用二分图实现，这里简单说下二分图的做法。

以下面这个图为例子

.X..
....
XX..
....

从左到右分别用1 2 3 ...表示，墙壁不编号也不打断编号。

横向可以得到多条边：

(1) (2 3) (4 5 6 7) (8 9) (10 11 12 13)

纵向可以得到多条边：

(1 4) (5) (2 6 8 12) (3 7 9 13) (10) (11)

然后我们可以将有横向和纵向有覆盖的边连接起来。接着就是找最大匹配的问题。

匈牙利算法是从出发点开始遍历，对于每一个出发点，广度优先找到一个终点，如果该点没有被访问，置该点为被访问，否则继续广度搜索下去。对于这个终点，判断其是否已经被匹配，如果被匹配了，将其匹配的起始点递归调用自身，否则，建立起点到终点的匹配，返回成功。

递归调用自身的时候，该起点会尝试找到下一个可以匹配的点，找到后修改匹配返回成功。如果找不到则返回失败。

这个递归调用的过程要搞清楚。需要两个数组一个保存匹配，一个在递归调用的时候保存已被访问的节点，但是这个数组在外层需要不断清空。

程序

#include <iostream>
#include <cstring>
using namespace std;
int n;
int row, col;
int number = 0;
int result = 0;
int G[4][4];
int len[32][4];
int mat[64], used[64];
struct Edge {
    int start, end;
}e[100];

// 找下一个匹配
bool find(int start) {
    for (int i = 0; i < number; i++) {
        if (e[i].start == start) {
            int end = e[i].end;
            // 终点没有被占用
            if (!used[end]) {
                // 标记占用
                used[end] = 1;
                // 终点没有被匹配或者终点对应的起始点能找到另一个匹配
                if (mat[end] == -1 || find(mat[end])) {
                    // 终点匹配起始点
                    mat[end] = start;
                    return true;
                }
            }
        }
    }
    return false;
}

// 匈牙利算法
void hungary() {
    memset(mat, -1, sizeof(mat));
    memset(used, 0, sizeof(used));
    for (int i = 0; i < row; i++) {
        if (find(i)) {
            result++;
        }
        memset(used, 0, sizeof(used));
    }
}

void build() {
    for (int i = 0; i < row; i++) {
        for (int j = row; j < col; j++) {
            int k = 0;
            bool connect = false;
            while (len[i][k] != 0 && k<4) {
                int u = 0;
                while (len[j][u] != 0 && u<4) {
                    if (len[j][u] == len[i][k]) {
                        Edge a;
                        a.start = i;
                        a.end = j;
                        e[number++] = a;
                        connect = true;
                        break;
                    }
                    u++;
                }
                k++;
                if (connect) {
                    break;
                }
            }
        }
    }
}

int main() {
    while (cin >> n && n) {
        int k = 0, num = 1;
        number = 0, result = 0;
        memset(G, 0, sizeof(G));
        memset(len, 0, sizeof(len));
        char temp;
        // 编号, 数组 G
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> temp;
                if (temp != 'X') {
                    G[i][j] = num;
                    num++;
                } else {
                    G[i][j] = 0;
                }
            }
        }
        // 建立横向边数组 len
        for (int i = 0; i < n; i++) {
            int u = 0;
            bool stone = true;
            for (int j = 0; j < n; j++) {
                if (G[i][j] != 0) {
                    stone = false;
                    len[k][u] = G[i][j];
                    u++;
                } else {
                    if (stone)    continue;
                    else {
                        stone = true;
                        k++;
                        u = 0;
                    }
                }
            }
            if (!stone)    k++;
        }
        row = k;
        // 建立纵向边数组 len 接上, 以 row 为分割
        for (int j = 0; j < n; j++) {
            int u = 0;
            bool stone = true;
            for (int i = 0; i < n; i++) {
                if (G[i][j] != 0) {
                    stone = false;
                    len[k][u] = G[i][j];
                    u++;
                } else {
                    if (stone)    continue;
                    else {
                        stone = true;
                        k++;
                        u = 0;
                    }
                }
            }
            if (!stone)    k++;
        }
        col = k;
        // 建立二分图
        build();
        // 找最大匹配
        hungary();
        cout << result << endl;
    }
    return 0;
}

ZOJ1610 - Count the Colors

题目

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.Your task is counting the segments of different colors you can see at last. Input The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.All the numbers are in the range [0, 8000], and they are all integers.Input may contain several data set, process to the end of file. Output

Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.If some color can't be seen, you shouldn't print it.Print a blank line after every dataset.

Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

Sample Output
1 1
2 1
3 1

1 1

0 2
1 1

分析

此题需要明确的一点是不能使用数组来记录颜色，数组效率很低，应该使用线段树来解决这道题。

在做关于线段树的题目的时候，要注意线段树的另一种变形点线段树。不过这道题还是用线段树来解决的。

解答此题有两个步骤：

• 建立完整线段树

  我们可以给初始线段树每个节点都赋予color = -1的属性。表示这是一颗没有颜色的节点。

• 成段更新染色

  在输入各个线段的颜色后，我们要对原线段树进行更新。可以使用color = -2来表示这是一颗混了各种颜色的树，和-1以及纯颜色区分开来。同时要注意的是，在处理一个树节点，比如题目给的第一个例子，我们经过第一步操作后(0, 4)的color值为4。接着是线段(0, 3)，color为1。此时做法是把(0, 4)的color设为-2，把其孩子(0, 2)和(2, 4)的color设为其父节点(0, 4)的color即4。接着猜开始使用(0, 3)的颜色来处理(0, 2)和(2, 4)。往下处理方式相同。

之后我们前序遍历这颗树就可以了。

如果此题使用数组，很明显使用数组将非常简单，但是效率十分低，我们每次染色都需要操作一大堆数。并且最后要遍历整个数组。如果数组范围较大，比如此题是8000，此题可能无法AC。而使用线段树，我们使用了color这个标记，为-1时表示未染色，用-2表示混杂颜色，我们在前序遍历进行到一个线段时发现color不为-2时，就不需要再继续搜索下去了。

程序

// 线段树，成段更新染色
// 不使用数组，因为数组效率太低，理解线段树！

#include <iostream>
#include <string.h>
using namespace std;
#define Maxsize 8005

int col[Maxsize];
int colCount[Maxsize];

// 顺序存储结构
struct node {
    int ld, rd;
    int color;
}Tree[Maxsize*3];

// 建立空线段树
void buildtree(int i, int a, int b) {
    Tree[i].ld = a;
    Tree[i].rd = b;
    Tree[i].color = -1;
    if (b - a == 1)	return;
    buildtree(i * 2, a, (a + b) / 2);
    buildtree(i * 2 + 1, (a + b) / 2, b);
}

// 插入 1 0 4 4
void insert(int i, int a, int b, int color) {
    int mid = (Tree[i].ld + Tree[i].rd) / 2;

    if (a <= Tree[i].ld && Tree[i].rd <= b) {
        Tree[i].color = color;
        return;
    }
    
    if (Tree[i].color != -2) {		// 代表有颜色覆盖
        Tree[i * 2].color = Tree[i].color;
        Tree[i * 2 + 1].color = Tree[i].color;
    }
    Tree[i].color = -2;
    if (b <= mid) {
        insert(i * 2, a, b, color);
    }
    else if (a >= mid) {
        insert(i * 2 + 1, a, b, color);
    }
    else {
        insert(i * 2, a, mid, color);
        insert(i * 2 + 1, mid, b, color);
    }

}

void search(int i) {
    if (Tree[i].color != -2 && Tree[i].color != -1) {
        for (int j = Tree[i].ld; j < Tree[i].rd; j++) {
            col[j] = Tree[i].color;
        }
    }
    if (Tree[i].color == -2) {
        search(2 * i);
        search(2 * i + 1);
    }
}

int main() {
    int n, m, a, b, c;
    while (cin >> n) {
        memset(colCount, 0, sizeof(colCount));
        memset(col, -1, sizeof(col));
        buildtree(1, 0, 8000);
        for (int i = 0; i < n; i++) {
            cin >> a >> b >> c;
            insert(1, a, b, c);
        }
        search(1);
        int t = -1;
        for (int i = 0; i <= 8000; i++) {
            if (col[i] == t)	continue;
            t = col[i];
            if (t != -1)	colCount[t]++;
        }
        for (int i = 0; i <= 18; i++) {
            if (colCount[i]) {
                cout << i << " " << colCount[i] << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

ZOJ1204 - Additive equations

We all understand that an integer set is a collection of distinct integers. Now the question is: given an integer set, can you find all its addtive equations? To explain what an additive equation is, let's look at the following examples:  1+2=3 is an additive equation of the set {1,2,3}, since all the numbers that are summed up in the left-hand-side of the equation, namely 1 and 2, belong to the same set as their sum 3 does. We consider 1+2=3 and 2+1=3 the same equation, and will always output the numbers on the left-hand-side of the equation in ascending order. Therefore in this example, it is claimed that the set {1,2,3} has an unique additive equation 1+2=3. It is not guaranteed that any integer set has its only additive equation. For example, the set {1,2,5} has no addtive equation and the set {1,2,3,5,6} has more than one additive equations such as 1+2=3, 1+2+3=6, etc. When the number of integers in a set gets large, it will eventually become impossible to find all the additive equations from the top of our minds -- unless you are John von Neumann maybe. So we need you to program the computer to solve this problem.

Input The input data consists of several test cases.  The first line of the input will contain an integer N, which is the number of test cases.  Each test case will first contain an integer M (1<=M<=30), which is the number of integers in the set, and then is followed by M distinct positive integers in the same line.

Output For each test case, you are supposed to output all the additive equations of the set. These equations will be sorted according to their lengths first( i.e, the number of integer being summed), and then the equations with the same length will be sorted according to the numbers from left to right, just like the sample output shows. When there is no such equation, simply output "Can't find any equations." in a line. Print a blank line after each test case.

Sample Input

3
3 1 2 3
3 1 2 5
6 1 2 3 5 4 6

Output for the Sample Input

1+2=3

Can't find any equations.

1+2=3
1+3=4
1+4=5
1+5=6
2+3=5
2+4=6
1+2+3=6

分析

这道题和前面一道交换卡片的题有点类似。也是使用深度优先遍历的方法解决。但这道题要注意记录路径，并且深度优先遍历实施前一般都要进行下排序，这道题目也是。纯DFS题目。

程序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int a[30];
int b[30];
int SIZE;
bool EQUAL = false;

bool inArray(int value) {
    for (int i = 0; i < SIZE; i++) {
        if (value == a[i]) {
            return true;
        }
    }
    return false;
}

// cur当前层数，des目标层数，sum当前总和
void DFS(int cur, int des, int sum, int last) {
    int i;
    // 当前层数等于目标层数时
    if (cur == des) {
        if (inArray(sum)) {
            for (i = 0; i < cur - 1; i++) {
                cout << b[i] << "+";
            }
            cout << b[cur - 1] << "=" << sum << endl;
            EQUAL = true;
        }
    }
    // 当前层数不等于目标层数时
    else {
        for (int i = last; i < SIZE; i++) {
            if (sum + a[i] <= a[SIZE - 1] && b[cur - 1] != a[i]) {
                b[cur] = a[i];        // 记录路径
                DFS(cur + 1, des, sum + a[i], i);
            }
        }
    }
}

int main()
{
    int length, k =0;
    cin >> length;
    for (int i = 0; i < length; i++) {
        int sum = 0;
        cin >> SIZE;
        for (int j = 0; j < SIZE; j++) {
            cin >> a[j];
        }
        // 先排序
        sort(a, a+SIZE);
        // 得出最大层数
        for (k = 0; k < SIZE; k++) {
            sum += a[k];
            if (sum > a[SIZE - 1]) {
                break;
            }
        }
        int deep = k;
        EQUAL = false;
        for (int i = 2; i <= k; i++) {
            DFS(0, i, 0, 0);
        }
        if (!EQUAL) {
            cout << "Can't find any equations." << endl;
        }
        cout << endl;
    }
    return 0;
}

ZOJ1217 - Eight

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as: 

 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15  x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4 
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8 
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12 
 13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x 
            r->            d->             r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

 1  2  3 
 x  4  6 
 7  5  8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

Sample Input

 2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

分析

这道题其实就是九宫格拼图的问题，给出一个拼图问能不能拼出原样。

一般我们都会想到从给出的这个图开始去做深度优先遍历或者广度优先遍历直至找出原样。

由于题目已经给定了这是一个3*3的方格，所以我们要考虑避免多次重复计算，所以应该想到这道题应该逆推过来。也就是从原图出发，建立一棵树记录全部可能情况。然后对于每次输入，只需要找找看是否存在这个图，如果有，依次输出变化关系即可。

从输入的图找出原图不难，但是要输出他们的关系则有一定的技巧了。此题我采用的是用map来保存图与图的映射关系，用广度优先遍历来建图。其余的参考代码吧。

程序

#include <iostream>
#include <queue>
#include <string>
#include <map>
#include <iterator>
using namespace std;

queue<string> Qu;
map<string, string> Map;
map<string, string>::iterator it;
string a = "12345678x";
string b;


void move(int from, int to, string a) {
    b = a;
    char temp;
    temp = b[to];
    b[to] = b[from];
    b[from] = temp;
    it = Map.find(b);
    if (it == Map.end()) {
        Map[b] = a;
        Qu.push(b);
    }
    else return;
}

void getDirect(string a, string b) {
    int x = a.find('x');
    int y = b.find('x');
    if (y == x - 3)    cout << "d";
    else if (y == x - 1)    cout << "r";
    else if (y == x + 3)    cout << "u";
    else if (y == x + 1)    cout << "l";
}

void search() {
    Qu.push(a);
    while (!Qu.empty()) {
        string t = Qu.front();
        Qu.pop();
        int x = t.find('x');
        if (x % 3 != 2) {            // 右移
            move(x, x + 1, t);
        }
        if (x % 3 != 0) {            // 左移
            move(x, x - 1, t);
        }
        if (x / 3 != 0) {            // 上移
            move(x, x - 3, t);
        }
        if (x / 3 != 2) {            // 下移
            move(x, x + 3, t);
        }
    }
}

int main() {
    search();
    string str = "";
    string data;
    string first;
    while (cin>>first) {
        str = "";
        str += first;
        for (int i = 1; i < 9; i++) {
            cin >> data;
            str += data;
        }
        while (str != a)
        {
            it = Map.find(str);
            if (it == Map.end()) {
                cout << "unsolvable";
                break;
            }
            else {
                getDirect(it->second, it->first);
                str = it->second;
            }
        }
        cout << endl;
    }
    return 0;
}

ZOJ1942 - Frogger

题目

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping. 

Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. 

To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.  The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone. 

Input

The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2 <= n <= 200). The next n lines each contain two integers xi, yi (0 <= xi, yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n. 

Output

For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one. 

Sample Input
2
0 0
3 4

3
17 4
19 4
18 5

0

Sample Output
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

分析

先介绍下Floyd-Warshall算法：

Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N^{3})，空间复杂度为O(N^{2})。

Floyd-Warshall是全源最短路径算法，支持负权值，但是不允许出现负数环。该算法的原理是动态规划。我们使用动态规划**进行分析。

设D[i][j][k]为从i到j的只以(1...k)集合中的节点为中间节点的最短路径的长度。

• 若最短路径经过点k，则D[i][j][k] = D[i][k][k-1] + D[k][j][k-1];
• 若最短路径不经过点k，则D[i][j][k] = D[i][j][k-1]

因此D[i][j][k] = min(D[i][k][k-1], D[i][k][k-1] + D[k][j][k-1])。

需要注意的是在建立三个循环的过程要按k->i->j的次序，因为我们是在围绕经不经过k这个石头展开的，也就是说对于任意两个石头，我们判断他们是经过k这个石头路径更短还是不经过更短，如果更短，我们就用这个更短的路径来替代当前的路径，当把全部石头都遍历完，我们就得到了任意两点之间的最短路径。

程序

#include <math.h>
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 2000
int x[maxn], y[maxn], n;
double d[maxn][maxn];

double dist(int i, int j) {
    return sqrt(pow(double(x[i] - x[j]), 2) + pow(double(y[i] - y[j]), 2));
}

int main()
{
    int count = 1;
    while (cin >> n && n) {
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        memset(d, 0, sizeof(d));
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> y[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = d[j][i] = dist(i, j);
            }
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                    }
                }
            }
        }
        printf("Scenario #%d\n", count);
        printf("Frog Distance = %0.3f\n", d[1][n]);
    }
    return 0;
}

ZOJ1203 - Swordfish

We all remember that in the movie Swordfish, Gabriel broke into the World Bank Investors Group in West Los Angeles, to rob $9.5 billion. And he needed Stanley, the best hacker in the world, to help him break into the password protecting the bank system. Stanley's lovely daughter Holly was seized by Gabriel, so he had to work for him. But at the last moment, Stanley made some little trick in his hacker mission: he injected a trojan horse in the bank system, so the money would jump from one account to another account every 60 seconds, and would continue jumping in the next 10 years. Only Stanley knew when and where to get the money. If Gabriel killed Stanley, he would never get a single dollar. Stanley wanted Gabriel to release all these hostages and he would help him to find the money back.   You who has watched the movie know that Gabriel at last got the money by threatening to hang Ginger to death. Why not Gabriel go get the money himself? Because these money keep jumping, and these accounts are scattered in different cities. In order to gather up these money Gabriel would need to build money transfering tunnels to connect all these cities. Surely it will be really expensive to construct such a transfering tunnel, so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length. Since Gabriel will get caught at the end of it anyway, so you can go ahead and write the program without feeling guilty about helping a criminal.

Input: The input contains several test cases. Each test case begins with a line contains only one integer N (0 <= N <=100), which indicates the number of cities you have to connect. The next N lines each contains two real numbers X and Y(-10000 <= X,Y <= 10000), which are the citie's Cartesian coordinates (to make the problem simple, we can assume that we live in a flat world). The input is terminated by a case with N=0 and you must not print any output for this case.

Output: You need to help Gabriel calculate the minimal length of tunnel needed to connect all these cites. You can saftly assume that such a tunnel can be built directly from one city to another. For each of the input cases, the output shall consist of two lines: the first line contains "Case #n:", where n is the case number (starting from 1); and the next line contains "The minimal distance is: d", where d is the minimal distance, rounded to 2 decimal places. Output a blank line between two test cases.

Sample Input:

5
0 0
0 1
1 1
1 0
0.5 0.5
0

Sample Output:

Case #1:
The minimal distance is: 2.83

分析

这道题明显是求最小生成树。给出多个城市的位置，要求找出连接所有点的最小距离。求最小生成树可以使用Kruskal或者Prim算法。这里只讨论Kruskal算法。

Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

关于Kruskal的步骤，如下:

1. 新建图G，G中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
4. 重复3，直至图G中所有的节点都在同一个连通分量中

我们可以使用优先队列和并查集来进行优化。取权值最小边，可以使用优先队列。判断这个边的两个节点在不在同一个连通分量可以使用并查集。

这里说下并查集和优先队列：

• 并查集

  并查集是一般会设置两个方法，即Find和Union。Union方法是将两个自己合并成一个集合。一般我们会选取集合中的一个元素作为根，其他节点作为他的孩纸。Union可以这样写：

  void Union(int i, int j) {
    parent[i] = j;
  }
  

  例如在该题中，我们每次取权值最小的边，在该边入列前，我们要先判断该边加入后会不会形成环路。因此我们可以判断下这条边的起始点和终点在不在一个集合里面。比如对于1-2-3-4-1这样连通的点，我们顺序找下去，可以建立出parent[1] = 2, parent[2] = 3, parent[3] = 4这个关系。接着对于4-1，我们先使用Find方法(前面的也有这个过程)，Find方法可以用下面的代码表示：

  int Find(int i) {
      while(parent[i] >= 0) i = parent[i];
    return i;
  }
  

  如果我们Find(4)会得到-1，（初始值全部设为-1），所以直接返回4，Find(1)会得到2，接着找Find(2)得到3，接着找Find(3)得到4，接着找Find(4)得到-1，那么返回4。两个数相同代表他们处在同一个集合。可以看到1，2，3都是4的孩子。

  并查集的Find和Union方法可以做进一步的优化如下：

  int CollapsingFind(int i) {
    //采用坍塌规则缩短
    for(int r = i; parent[r] >= 0; r = parent[r]);
    while(i != r) {
        int s = parent[i];
      parent[i] = r;
      i = s;
    }
    return r;
  }
  
  void WeightedUnion(int i, int j) {
    // 基于权重规则构造以i和j为根的集合的并
    int temp = parent[i] + parent[j];
    if(parent[j] < parent[i]) {
        parent[i] = j;
      parent[j] = temp;
    }
    else {
      parent[j] = i;
      parent[i] = temp;
    }
  }
  
  

• 优先队列

  优先队列的头文件，定义，以及使用方法

  #include <queue>                                          // 头文件
  priority_queue<EdgeNode> PQ;                              // 定义
  bool operator < (const EdgeNode &a, const EdgeNode &b) {  // 运算符重载
    if (a.cost > b.cost) {
        return true;
    }
    else {
        return false;
    }
  }
  

使用Kruskal算法，我们每次从优先队列pop出一条边，调用Find方法判断两个端点是否在同一集合上面，如果不在，则调用Union方法将他们加到同一并查集里面，把他们的权值加进来。这样循环调用即可。

程序

#include <iostream>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <cstring>
using namespace std;
#define Maxsize 100

struct EdgeNode {
    int start, end;
    double cost;
};
struct Edge {
    double x, y;
};
Edge edge[1000];
double cost[1000][1000];
int parent[Maxsize];            // 并查集

bool operator < (const EdgeNode &a, const EdgeNode &b) {
    if (a.cost > b.cost) {
        return true;
    }
    else {
        return false;
    }
}

int Find(int i) {
    // 简单实现:
    // while(parent[i] >= 0) i = parent[i];
    // return i;
    // 改进实现:
    // 找到含元素i的树的根，采用坍塌规则缩短
    // 从i到根的所有结点到根的距离
    int r;
    for (r = i; parent[r] >= 0; r = parent[r]);    //找到根
    while (i != r) {
        int s = parent[i];
        parent[i] = r;
        i = s;
    }
    return r;
}
void Union(int i, int j) {
    parent[i] = j;
}

priority_queue<EdgeNode> PQ;

int main()
{
    int n;
    while (cin >> n && n) {
        memset(parent, -1, sizeof(parent));
        for (int i = 1; i <= n; i++) {
            cin >> edge[i].x >> edge[i].y;
        }
        // 转为邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                cost[i][j] = sqrt((edge[i].x - edge[j].x)*(edge[i].x - edge[j].x) + (edge[i].y - edge[j].y)*(edge[i].y - edge[j].y));
                cost[j][i] = cost[i][j];
            }
        }
        // 存入优先队列
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                EdgeNode edge;
                edge.start = i;
                edge.end = j;
                edge.cost = cost[i][j];
                PQ.push(edge);                // 存入优先队列
            }
        }
        double Mincost = 0;
        for (int count = 1; count <= n; count++) {
            EdgeNode edge;
            edge = PQ.top();
            PQ.pop();                // 从优先队列中取权值最小的边
            int u = Find(edge.start),
                v = Find(edge.end);
            if (u != v) {
                Union(u, v);
                Mincost += edge.cost;
            }
        }
        printf("%.2f\n", Mincost);
    }
    return 0;
}

ZOJ1789 - The Suspects

题目

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).Once a member in a group is a suspect, all members in the group are suspects.However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n-1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.A case with n = 0 and m = 0 indicates the end of the input, and need not be processed. 

Output

For each case, output the number of suspects in one line.

Sample Input

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

4
1
1

分析

以题目给的第一个例子为例，有100个学生，4个学习小组。这4个学习小组分别是：

• 2人小组，学生1，2
• 5人小组，学生10，13，11，12，14
• 2人小组，学生0，1
• 2人小组，学生99，2

学生0有传染病嫌疑。问这些学生中有多少人有可能感染传染病。

这道题可以有多种做法，比较简单的做法就是我现在写的代码。也就是按顺序遍历下来，找到带传染病的学生0，然后把该组的所有学生都置为有嫌疑，每个新增的学生都继续递归调用搜索。最后递归的次数也就是传染病的可能人数。

在判断该学生是否已经被有传染病嫌疑时，可以使用数组标记位判断，亦可以使用并查集。

程序

// 传染病嫌疑人
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
int group[500][30000];		// group数组
int m;						// k是group数量
int suspects[30000];
int number = 1;

void search(int t) {
    for (int i = 0; i < m; i++) {
        if (group[i][0] == -2) {		// -2代表已全部有嫌疑
            continue;
        }
        else {
            int j = 1;
            while (group[i][j] != -1) {
                if (group[i][j] == t) {	// 该组含嫌疑人
                    group[i][0] = -2;
                    int u = 1;
                    while (group[i][u] != -1) {						// 遍历该组
                        if (suspects[group[i][u]] == 1) {			// 已搜索
                            u++;
                            continue;
                        }
                        else {								
                            number++;
                            suspects[group[i][u]] = 1;		// 进入搜索范围
                            search(group[i][u]);			// 进入搜索
                            u++;
                        }
                    }
                }
                j++;
            }
        }
    }
}


int main(){
    int n, k;
    while (cin >> n >> m) {
        number = 1;
        if (n == 0 && m == 0) {
            break;
        }
        else {
            memset(group, -1, sizeof(group));
            memset(suspects, 0, sizeof(suspects));
            suspects[0] = 1;
            for (int i = 0; i < m; i++) {
                cin >> k;
                for (int j = 1; j <= k; j++) {
                    cin >> group[i][j];
                }
            }
        }
        search(0);
        cout << number << endl;
    }
    return 0;
}

ZOJ2193 - Window Pains

题目

Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:

1  1  .  .           .  2  2  .         .  . 3  3
1  1  .  .           .  2  2  .         .  . 3  3
.  .  .  .           .  .  .  .         .  .  .  .
.  .  .  .           .  .  .  .         .  .  .  . 

.  .  .  .           .  .  .  .         .  .  .  .
4  4  .  .           .  5  5  .         .  6  6  .
4  4  .  .           .  5  5  .         .  6  6  .
.  .  .  .           .  .  .  .         .  .  .  . 

.  .  .  .           .  .  .  .         .  .  .  .
.  .  .  .           .  .  .  .         .  .  .  .
7  7  .  .           .  8  8  .         .  .  9  9
7  7  .  .           .  8  8  .         .  .  9  9

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and then window 2 were brought to the foreground, the resulting representation would be:

1  2  2  . 
1  2  2  . 
.  .  .  . 
.  .  .  .

If window 4 were then brought to the foreground:

1  2  2  . 
4  4  2  . 
4  4  .  . 
.  .  .  .

. . . and so on . . .

Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

1. Start line - A single line:START
2. Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
3. End line - A single line:END

After the last data set, there will be a single line:

ENDOFINPUT

Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:

THESE WINDOWS ARE CLEAN

Otherwise, the output will be a single line with the statement:

THESE WINDOWS ARE BROKEN

Sample Input

START 1 2 3 3 4 5 6 6 7 8 9 9 7 8 9 9 END START 1 1 3 3 4 1 3 3 7 7 9 9 7 7 9 9 END ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN THESE WINDOWS ARE BROKEN

分析

如果知道拓扑排序的话应该很容易知道这道题要用拓扑排序来解决。

不看题目看例子也可以看懂题目的意思了~

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。

1. 每个顶点出现且只出现一次；
2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

进行拓扑排序，有以下步骤：

1. 输入AOV网络。令n为顶点个数。
2. 在AOV网络中选择一个入度为0的结点，并输出之。
3. 从图中删去该顶点，同时删去所有它发出的有向边。
4. 重复以上2，3步，直到下面的情况之一出现：
   • 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。
   • 图中还有未输出的顶点，但已没有入度为0的结点（说明网络中必定存在有向环）。

接下来来看下这道题。

进行拓扑排序第一步是建立邻接矩阵和他们的度数。我们要知道这个邻接矩阵表示的是什么和什么之间的关系。对于这道题，邻接矩阵是用来表示窗口i可以覆盖哪些窗口。比如对于此题的第一个例子，我们建立邻接矩阵如下图：

所以建立出来的邻接矩阵如下。G[I][J]为1时表示窗口I可以覆盖窗口J。

G[10][10]
G[0]    0 0 0 0 0 0 0 0 0 0
G[1]    0 0 0 0 0 0 0 0 0 0
G[2]    0 1 0 0 0 0 0 0 0 0
G[3]    0 0 1 0 0 0 0 0 0 0
G[4]    0 1 0 0 0 0 0 0 0 0
G[5]    0 1 1 0 1 0 0 0 0 0
G[6]    0 0 1 1 0 1 0 0 0 0
G[7]    0 0 0 0 1 0 0 0 0 0
G[8]    0 0 0 0 1 1 0 1 0 0
G[9]    0 0 0 0 0 1 1 0 1 0

同时记录下indegree[9]表示窗口i的入度。

接着使用拓扑排序算法即可。

程序

// 拓扑排序

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

int a[4][4];

bool exist[10];
string cover[4][4];
int G[10][10];
int indegree[10];
int type;				// 输入的数的类型

void buildG() {			// 构造有向图
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int p = 0; p < cover[i][j].length(); p++) {
                int from = a[i][j],
                    to = cover[i][j][p] - '0';
                // [i][j]到所有[i][j]可能覆盖点，建立邻接矩阵
                if (G[from][to] == 0 && from != to && exist[from] && exist[to]) {
                    G[from][to] = 1;
                    indegree[from] ++;
                }
            }
        }
    }
}

bool check() {			// 判断是否有环，无环返回true，有环返回false
    for (int i = 0; i < type; i++) {
        int count = 0;	// 计算当前入度等于0的窗口数
        int number = 0;	// 记录当前窗口数
        for (int j = 1; j <= 9; j++) {
            if (exist[j] && indegree[j] == 0) {
                count++;
            }
            if (exist[j]) {
                number++;
            }
        }
        // 如果已经没有入度为0的窗口而当前窗口还不为0，则返回false
        if (count == 0 && number > 0) {
            return false;
        }
        int k=0;
        // 找到入度为0的点
        for (int j = 1; j <= 9; j++) {
            if (exist[j] && indegree[j] == 0) {
                k = j;
                break;
            }
        }
        exist[k] = false;
        for (int j = 1; j <= 9; j++)
            if (exist[j] && G[j][k])
                // 删除相应顶点入边(入度减1)  
                indegree[j]--;
    }
}

int main() {
    string str;
    for (int i = 1; i <= 9; i++) {			// cover表示(i,j)处可能的覆盖
        int t = (i-1) / 3;
        int k = (i-1) % 3;
        cover[t][k] += char(i + '0');
        cover[t][k + 1] += char(i + '0');
        cover[t + 1][k] += char(i + '0');
        cover[t + 1][k + 1] += char(i + '0');
    }
    while (cin >> str && str != "ENDOFINPUT") {
        memset(exist, 0, sizeof(exist));
        memset(indegree, 0, sizeof(indegree));
        memset(G, 0, sizeof(G));
        type = 0;
        for (int i = 0; i < 4; i++) {					// 输入数据
            for (int j = 0; j < 4; j++) {
                cin >> a[i][j];
                if (!exist[a[i][j]])	type++;
                exist[a[i][j]] = true;					
            }
        }
        buildG();
        if (check()) {
            cout << "THESE WINDOWS ARE CLEAN" << endl;
        }
        else {
            cout << "THESE WINDOWS ARE BROKEN" << endl;
        }
        string s;
        cin >> s;
    }
    return 0;
}