poj2585

maksyuki 发表于 oj 分类，标签: 图论-拓扑排序

15 9月 2015

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	.	.
1	1	.	.
.	.	.	.
.	.	.	.

.	2	2	.
.	2	2	.
.	.	.	.
.	.	.	.

.	.	3	3
.	.	3	3
.	.	.	.
.	.	.	.

.	.	.	.
4	4	.	.
4	4	.	.
.	.	.	.

.	.	.	.
.	5	5	.
.	5	5	.
.	.	.	.

.	.	.	.
.	.	6	6
.	.	6	6
.	.	.	.

.	.	.	.
.	.	.	.
7	7	.	.
7	7	.	.

.	.	.	.
.	.	.	.
.	8	8	.
.	8	8	.

.	.	.	.
.	.	.	.
.	.	9	9
.	.	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 1and then window 2were 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:

Start line - A single line:
START
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.
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

Source

South Central USA 2003

题目类型：拓扑排序

算法分析：由于输入中的窗口是最靠外面的，且题目中说调动了所有的窗口。这就意味着最外面的窗口中的数字覆盖了其他在该位置处的数字，使用这种覆盖关系构造有向图。首先构造9个窗口，然后对于输入的窗口中的每一个位置处的数字a遍历所有的9个窗口在该位置的取值vi，如果在该处存在值vi且不与a相等，则构造一条有向边，起点为a，终点为vi。最后对于构造好的有向图使用拓扑排序即可

#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 16;

const int dx[] = {0, 1, 0, 1};
const int dy[] = {0, 1, 1, 0};

int ans[maxn][maxn];
int num[maxn][maxn][maxn];
int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()
{
	int i;
	for (i = 0; i < 9; i++)
	{
		int val_x = i / 3, val_y = i % 3, j; // important!!!!!!
		
		for (j = 0; j < 4; j++)
			num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;
	}
}

void Solve ()
{
	int i, j, k;
	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			for (k = 0; k < 9; k++)
			{
				if (num[k][i][j] && ans[i][j] != num[k][i][j])
				{
					indegree[num[k][i][j]]++;
					vec[ans[i][j]].push_back (num[k][i][j]);
				}
			}
}

void Topo ()
{
	is_valid = true;
	queue <int> q;

	int i;
	for (i = 1; i <= 9; i++)
		if (!indegree[i])
			q.push (i);

	while (!q.empty ())
	{
		int temp = q.front ();
		q.pop ();

		for (i = 0; i < vec[temp].size (); i++)
		{
			indegree[vec[temp][i]]--;
			
			if (!indegree[vec[temp][i]])
				q.push (vec[temp][i]);
		}
	}

	for (i = 1; i <= 9; i++)
		if (indegree[i])
			break;

	if (i <= 9)
		is_valid = false;

}


int main()
{
//	ifstream cin ("aaa.txt");

	char input[36];
	
	memset (num, 0, sizeof (num));
	Build ();

	while (cin >> input)
	{
		if (!strcmp (input, "ENDOFINPUT"))
			break;

		int i;
		for (i = 0; i < 4; i++)
		{
			int j;
			for (j = 0; j < 4; j++)
				cin >> ans[i][j];
		}

		cin >> input;
		
		for (i = 0; i < maxn; i++)
			vec[i].clear ();

		memset (indegree, 0, sizeof (indegree));

		Solve ();
		
		Topo ();

		if (is_valid)
			cout << "THESE WINDOWS ARE CLEAN" << endl;

		else
			cout << "THESE WINDOWS ARE BROKEN" << endl;
	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

const int maxn = 16;

const int dx[] = {0, 1, 0, 1};

const int dy[] = {0, 1, 1, 0};

int ans[maxn][maxn];

int num[maxn][maxn][maxn];

int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()

{

int i;

for (i = 0; i < 9; i++)

{

int val_x = i / 3, val_y = i % 3, j; // important!!!!!!

for (j = 0; j < 4; j++)

num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;

}

void Solve ()

{

int i, j, k;

for (i = 0; i < 4; i++)

for (j = 0; j < 4; j++)

for (k = 0; k < 9; k++)

{

if (num[k][i][j] && ans[i][j] != num[k][i][j])

{

indegree[num[k][i][j]]++;

vec[ans[i][j]].push_back (num[k][i][j]);

}

void Topo ()

{

is_valid = true;

queue <int> q;

int i;

for (i = 1; i <= 9; i++)

if (!indegree[i])

q.push (i);

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

for (i = 0; i < vec[temp].size (); i++)

{

indegree[vec[temp][i]]--;

if (!indegree[vec[temp][i]])

q.push (vec[temp][i]);

}

for (i = 1; i <= 9; i++)

if (indegree[i])

break;

if (i <= 9)

is_valid = false;

}

int main()

{

// ifstream cin ("aaa.txt");

char input[36];

memset (num, 0, sizeof (num));

Build ();

while (cin >> input)

{

if (!strcmp (input, "ENDOFINPUT"))

break;

int i;

for (i = 0; i < 4; i++)

{

int j;

for (j = 0; j < 4; j++)

cin >> ans[i][j];

}

cin >> input;

for (i = 0; i < maxn; i++)

vec[i].clear ();

memset (indegree, 0, sizeof (indegree));

Solve ();

Topo ();

if (is_valid)

cout << "THESE WINDOWS ARE CLEAN" << endl;

else

cout << "THESE WINDOWS ARE BROKEN" << endl;

}

return 0;

}

poj2576

poj2689

超客的水墨烟雨

poj2585

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31