20 | 3月 | 2016 | 超客的水墨烟雨

poj3687

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

20 3月 2016

Labeling Balls

Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:

1. No two balls share the same label. 阅读全文 »

poj1128

maksyuki 发表于 oj 分类，标签: 图论-拓扑排序, 基础算法-搜索(DFS\BFS)\记忆化

20 3月 2016

Frame Stacking

Consider the following 5 picture frames placed on an 9 x 8 array.Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.

Viewing the stack of 5 frames we see the following.

........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........
1 2 3 4 5

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

In what order are the frames stacked from bottom to top? The answer is EDABC.
Your problem is to determine the order in which the frames are stacked from bottom to top given a picture of the stacked frames. Here are the rules:

1. The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters.

2. It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.

3. The frames will be lettered with capital letters, and no two frames will be assigned the same letter.

Input

Each input block contains the height, h (h<=30) on the first line and the width w (w<=30) on the second. A picture of the stacked frames is then given as h strings with w characters each.
Your input may contain multiple blocks of the format described above, without any blank lines in between. All blocks in the input must be processed sequentially.

Output

Write the solution to the standard output. Give the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities in alphabetical order, each one on a separate line. There will always be at least one legal ordering for each input block. List the output for all blocks in the input sequentially, without any blank lines (not even between blocks).

Sample Input

9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

Sample Output

EDABC

Source

Southern African 2001

题目类型：拓扑排序+dfs

算法分析：通过题意先将每个frame画出来，然后对于每个图画A，若有其他图画B的字符覆盖，则从A到B连一条有向边，最后dfs时优先选择字符小的即可，注意这里可能存在多个图画互相不覆盖的情况，若使用B向A建图，则会WA！！！

/*************************************************
Author        :supermaker
Created Time  :2016/3/20 10:05:27
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 66;

int row, col, tot, ind[maxn];
char g[maxn][maxn], gg[maxn][maxn][maxn], out[maxn];
bool vis[maxn], vvis[maxn];
vector <int> edge[maxn];

void PP (char val)
{
	int minx = INF, maxx = -INF, miny = INF, maxy = -INF;
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++)
			if (g[i][j] == val)
			{
				minx = min (minx, i);
				maxx = max (maxx, i);
				miny = min (miny, j);
				maxy = max (maxy, j);
			}
	
	for (int i = minx; i <= maxx; i++)
		gg[tot][i][miny] = gg[tot][i][maxy] = val;
	for (int i = miny; i <= maxy; i++)
		gg[tot][minx][i] = gg[tot][maxx][i] = val;
	tot++;
}

void Build ()
{
	for (int i = 0; i < maxn; i++)
		edge[i].clear ();
	memset (ind, 0, sizeof (ind));
	for (int i = 0; i < tot; i++)
		for (int j = 1; j <= row; j++)
			for (int k = 1; k <= col; k++)
				if (gg[i][j][k] != '.' && gg[i][j][k] != g[j][k])
				{
					ind[g[j][k]-'A']++;
					edge[gg[i][j][k]-'A'].push_back (g[j][k] - 'A');
				}
}

void dfs (int cur)
{
	if (cur == tot)
	{
		for (int i = 0; i < tot; i++)
			printf ("%c", out[i]);
		puts ("");
		return ;
	}
	for (int i = 0; i <= 25; i++)
		if (vis[i] &&  !vvis[i] && !ind[i])
		{
			for (int j = 0; j < edge[i].size (); j++)
				ind[edge[i][j]]--;
			//printf ("%c", (char) (i + 'A'));
			out[cur] = (char) (i + 'A');
			vvis[i] = true;
			dfs (cur + 1);		
			vvis[i] = false;
			for (int j = 0; j < edge[i].size (); j++)
				ind[edge[i][j]]++;
		}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &row, &col) != EOF)
	{
		tot = 0;
		memset (vis, false, sizeof (vis));
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				for (int k = 0; k < maxn; k++)
					gg[i][j][k] = '.';

		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
				scanf (" %c", &g[i][j]);
		
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
				if (g[i][j] != '.' && !vis[g[i][j]-'A'])
				{
					PP (g[i][j]);
					vis[g[i][j]-'A'] = true;
				}
		
		Build ();
		memset (vvis, false, sizeof (vvis));
		dfs (0);
	}
    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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

/*************************************************

Author :supermaker

Created Time :2016/3/20 10:05:27

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 66;

int row, col, tot, ind[maxn];

char g[maxn][maxn], gg[maxn][maxn][maxn], out[maxn];

bool vis[maxn], vvis[maxn];

vector <int> edge[maxn];

void PP (char val)

{

int minx = INF, maxx = -INF, miny = INF, maxy = -INF;

for (int i = 1; i <= row; i++)

for (int j = 1; j <= col; j++)

if (g[i][j] == val)

{

minx = min (minx, i);

maxx = max (maxx, i);

miny = min (miny, j);

maxy = max (maxy, j);

}

for (int i = minx; i <= maxx; i++)

gg[tot][i][miny] = gg[tot][i][maxy] = val;

for (int i = miny; i <= maxy; i++)

gg[tot][minx][i] = gg[tot][maxx][i] = val;

tot++;

}

void Build ()

{

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

edge[i].clear ();

memset (ind, 0, sizeof (ind));

for (int i = 0; i < tot; i++)

for (int j = 1; j <= row; j++)

for (int k = 1; k <= col; k++)

if (gg[i][j][k] != '.' && gg[i][j][k] != g[j][k])

{

ind[g[j][k]-'A']++;

edge[gg[i][j][k]-'A'].push_back (g[j][k] - 'A');

}

void dfs (int cur)

{

if (cur == tot)

{

for (int i = 0; i < tot; i++)

printf ("%c", out[i]);

puts ("");

return ;

}

for (int i = 0; i <= 25; i++)

if (vis[i] && !vvis[i] && !ind[i])

{

for (int j = 0; j < edge[i].size (); j++)

ind[edge[i][j]]--;

//printf ("%c", (char) (i + 'A'));

out[cur] = (char) (i + 'A');

vvis[i] = true;

dfs (cur + 1);

vvis[i] = false;

for (int j = 0; j < edge[i].size (); j++)

ind[edge[i][j]]++;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &row, &col) != EOF)

{

tot = 0;

memset (vis, false, sizeof (vis));

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

for (int j = 0; j < maxn; j++)

for (int k = 0; k < maxn; k++)

gg[i][j][k] = '.';

for (int i = 1; i <= row; i++)

for (int j = 1; j <= col; j++)

scanf (" %c", &g[i][j]);

for (int i = 1; i <= row; i++)

for (int j = 1; j <= col; j++)

if (g[i][j] != '.' && !vis[g[i][j]-'A'])

{

PP (g[i][j]);

vis[g[i][j]-'A'] = true;

}

Build ();

memset (vvis, false, sizeof (vvis));

dfs (0);

}

return 0;

}

poj1094

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

20 3月 2016

Sorting It All Out

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.Inconsistency found after 2 relations.Sorted sequence cannot be determined.

Source

East Central North America 2001

题目类型：拓扑排序+枚举

算法分析：边读入边求解拓扑序，判断拓扑序是否存在，存在时是否唯一。注意这里要优先判断是否存在，而且唯一拓扑序不一定是按照常规字母表大小规则排列的！！！

/*************************************************
Author        :supermaker
Created Time  :2016/3/20 8:50:22
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 166;

int ind[maxn], tmp[maxn], res, num, n, m;
vector <int> edge[maxn];
char ans[maxn];

void Topo (int cnt)
{
	int tot = 0, is_one = 0, len = 0;
	bool is_valid = true;
	for (int i = 0; i < n; i++)
		tmp[i] = ind[i];
	queue <int> qu;
	for (int i = 0; i < n; i++)
		if (tmp[i] == 0)
		{
			qu.push (i);
			is_one++;
		}

	if (is_one >= 2)
		is_valid = false;
	
	while (!qu.empty ())
	{
		int tt = qu.front (); qu.pop ();
		ans[len++] = (char) (tt + 'A');
		tot++, is_one = 0;
		for (int i = 0; i < edge[tt].size (); i++)
		{
			tmp[edge[tt][i]]--;
			if (tmp[edge[tt][i]] == 0)
			{
				qu.push (edge[tt][i]);
				is_one++;
			}
		}
		if (is_one >= 2)
			is_valid = false;
	}

	if (tot < n)
	{
		res = 2;
		num = cnt;
	}
	else
	{
		if (!is_valid)
		{
			res = 3;
			return ;
		}
		res = 1;
		num = cnt;
		for (int i = 0; i < len / 2; i++)
		{
			char tc = ans[i];
			ans[i] = ans[len-1-i];
			ans[len-1-i] = tc;
		}
		ans[len] = 0;
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		if (n == 0 && m == 0) break;
		memset (ind, 0, sizeof (ind));
		for (int i = 0; i < maxn; i++)
			edge[i].clear ();
		res = -1, num = 1;
		char cmd[6];
		for (int i = 1; i <= m; i++)
		{
			scanf ("%s", cmd);
			ind[cmd[0]-'A']++;
			edge[cmd[2]-'A'].push_back (cmd[0]-'A');
			if (res == -1 || res == 3)
				Topo (i);		
		}
		if (res == 1)
			printf ("Sorted sequence determined after %d relations: %s.\n", num, ans);
		else if (res == 2)
			printf ("Inconsistency found after %d relations.\n", num);
		else
			puts ("Sorted sequence cannot be determined.");
	}
    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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

/*************************************************

Author :supermaker

Created Time :2016/3/20 8:50:22

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 166;

int ind[maxn], tmp[maxn], res, num, n, m;

vector <int> edge[maxn];

char ans[maxn];

void Topo (int cnt)

{

int tot = 0, is_one = 0, len = 0;

bool is_valid = true;

for (int i = 0; i < n; i++)

tmp[i] = ind[i];

queue <int> qu;

for (int i = 0; i < n; i++)

if (tmp[i] == 0)

{

qu.push (i);

is_one++;

}

if (is_one >= 2)

is_valid = false;

while (!qu.empty ())

{

int tt = qu.front (); qu.pop ();

ans[len++] = (char) (tt + 'A');

tot++, is_one = 0;

for (int i = 0; i < edge[tt].size (); i++)

{

tmp[edge[tt][i]]--;

if (tmp[edge[tt][i]] == 0)

{

qu.push (edge[tt][i]);

is_one++;

}

if (is_one >= 2)

is_valid = false;

}

if (tot < n)

{

res = 2;

num = cnt;

}

else

{

if (!is_valid)

{

res = 3;

return ;

}

res = 1;

num = cnt;

for (int i = 0; i < len / 2; i++)

{

char tc = ans[i];

ans[i] = ans[len-1-i];

ans[len-1-i] = tc;

}

ans[len] = 0;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

if (n == 0 && m == 0) break;

memset (ind, 0, sizeof (ind));

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

edge[i].clear ();

res = -1, num = 1;

char cmd[6];

for (int i = 1; i <= m; i++)

{

scanf ("%s", cmd);

ind[cmd[0]-'A']++;

edge[cmd[2]-'A'].push_back (cmd[0]-'A');

if (res == -1 || res == 3)

Topo (i);

}

if (res == 1)

printf ("Sorted sequence determined after %d relations: %s.\n", num, ans);

else if (res == 2)

printf ("Inconsistency found after %d relations.\n", num);

else

puts ("Sorted sequence cannot be determined.");

}

return 0;

}

超客的水墨烟雨

poj3687

poj1128

poj1094

分类目录

标签云

书签

近期评论

2016年3月
一	二	三	四	五	六	日
« 2月				4月 »
	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