题目大意

给定一个二维迷宫， "#" 表示不可走的位置，“.” 表示可走的位置，起点为 “S”，终点为 “E”。问左手扶墙走、右手扶墙走和最短路线的步数各是多少。

阅读全文

2016-07-30 3,963 次浏览 0 条评论

POJ 1094 Sorting It All Out（拓扑排序）解题报告

题目链接

题目翻译

描述

一个升序序列中不同元素之间可以用带小于号的关系式来从小到大排列元素。例如，有序序列 A, B, C, D 中包含关系 A < B, B < C 和 C < D。在本题中，我们会给你一个形如 "A < B" 的关系集合，请你决定由此构成的有序序列是否唯一。

输入

输入包含多组实例。每组实例的第一行包含两个正整数 n, m，前者表示待排序对象的数量，2 <= n <= 26，待排序对象是字母表中前 n 个大写字母；后者表示题目实例中给出的 "A < B" 形式的关系数量。接下来有 m 行，每行包含一对关系，每对关系由三个字符组成：一个大写字母、一个小于号和另一个大写字母。不会出现超出前 n 个大写字母的数据。当 n = m = 0 时输入结束。

输出

对于每组测试实例，输出一行，每行会是以下三种情况之一：

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

其中 "xxx" 指有序序列被确定或被证明矛盾时已处理的关系数量，"yyy...y" 指最终确定的升序序列。

阅读全文

2016-07-29 3,287 次浏览 0 条评论

解题报告

POJ 1753 Flip Game（状态压缩+BFS）解题报告

题面

Flip Game
Time Limit: 1000MS Memory Limit: 65536K
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
Choose any one of the 16 pieces.
Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
Source
Northeastern Europe 2000