Tester Program
Description
Tester Program
For this contest, we first designed the following problem (note that you do not have to solve it!):
Another Wall in the Maze
In ACM/ICPC contests, you’ll often see questions such as “find the shortest path out of this maze.” Let’s turn this on its head and ask “given a path, find a maze for which the given path is the shortest path.” Our paths will run vertically and horizontally between the regularly spaced points of a rectangular grid. The problem is to compute a set of unit-length baffles (walls) separating grid points that forces the given path to be the unique shortest path from its starting point to the end point. To make things more interesting, we will require that there should be no redundant walls constructed in the sense that it should not be possible to remove any wall and still have the given path as the unique shortest path. In the following figure for example, consider the path through the 8 ? 5 grid on the left maze of the top row. The wall placements in the two mazes to its right (top row) make that path unique. The two mazes on the lower row are faulty.
The path is not unique in the one on the left, and there are some redundant walls on the right.
Input (of the original problem)
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. The first line of each test case consists of two integers W and H (1 ≤ W, H ≤ 100) giving the width and height of the grid respectively. The second line of the test case contains a path. The path always starts in the lowerleft corner, (0, 0). It is specified as a string of U (up), D (down), L (left), and R (right) characters (with no embedded white space). You may assume that the path remains within the bounds of the maze and does not intersect itself. It may end anywhere in the maze (i.e., not necessarily in a corner or against a wall).
Output (of the original problem)
First line of the output for the i-th test case (starting from one) should contain an integer M, the number of walls used in the solution. Following the first line, there are M lines each containing a wall specification in the form of four consecutive integers corresponding to two pairs of (x, y) coordinates specifying adjacent grid points separated by the wall (0 ≤ x < W and 0 ≤ y < H). Note that the possible output is not unique. There should no blank line in the output.
Sample Input (of the original problem)
2
8 5
RRRUULLURRRRDDRRUUU
4 3
RRRUU
Sample Output (of the original problem)
19
0 0 0 1
1 0 1 1
2 0 2 1
2 1 3 1
3 0 4 0
3 1 4 1
3 2 4 2
3 2 3 3
2 2 2 3
4 2 4 3
0 3 0 4
1 3 1 4
2 3 2 4
3 3 3 4
4 3 4 4
5 3 5 4
5 3 6 3
5 2 6 2
6 1 6 2
2
2 2 3 2
2 2 2 1
This is the end of the original problem statement! Being lazy, we did not want to spend time to write a tester program for this problem, and decided to have you write this for us!
Write a program that receives both input and output as one input test case, and write as output CORRECT or INCORRECT to indicate whether or not the output is correct.
Input
You read both input and output of the original problem from the standard input;it has each output just after each case’s input of the original problem.
Note that the output of original does not have formatting problems, i.e.,
The number of lines in the output file is correct and is as supposed to be.
There are no leading or trailing white space characters in output lines.
Wall specifications are correct, meaning that the four numbers correctly specify a possible wall within the boundary of the maze.
Output
Your program should write a single line for each test case of the input containing a single word CORRECT or INCORRECT, indicating the original problem has correctly produced the output for that test case or not.
Sample Input
2 8 5 RRRUULLURRRRDDRRUUU 19 0 0 0 1 1 0 1 1 2 0 2 1 2 1 3 1 3 0 4 0 3 1 4 1 3 2 4 2 3 2 3 3 2 2 2 3 4 2 4 3 0 3 0 4 1 3 1 4 2 3 2 4 3 3 3 4 4 3 4 4 5 3 5 4 5 3 6 3 5 2 6 2 6 1 6 2 4 3 RRRUU 2 2 2 3 2 2 2 2 1
Sample Output
CORRECT INCORRECT
我的代码
这个题目要解决两个部分：判断是否是唯一最短路径；判断是否有墙是多余的。
由于之前没接触过这个题型，导致我花了很大功夫用宽搜去解决第一个问题，然而第二个问题却得不到解决方法。最后只能去网上找解法。
这一题，是要用宽搜去找出所有点到源点和终点的距离。
判断是否是唯一最短路径的方法：如果题目所给的路径确实是最短路径，那么在除了这个路径上的点意外，任意一个点到源点和终点的距离之和都应该比最短路径长。
for (int i=0;i<w;i++){
for (int j=0;j<h;j++){
if (isPath[i][j]==0){
if (toSource[i][j]+toTarget[i][j]<=len){
correct=0;
break;
}
}
}
if (correct==0){
break;
}
}判断一面墙是否是多余的，就要看如果没有这面墙，原本被墙隔住的两个点到源点和终点的距离是否会变得不比最短路径大。因为如果移出墙之后这个新的路径小于等于给定的路径长度之后，给定的那个路径就不是唯一最短路径了。判断一面墙是否多余还有一个条件，即如果有某个点被墙包围住，那么一定是多余的，不过这一题的测试样例并没有出现，所以不屑也没关系。
for (int i=0;i<wall.size()/2;i++){
if (correct==0){
break;
}
x1=wall[2*i].x;
y1=wall[2*i].y;
x2=wall[2*i+1].x;
y2=wall[2*i+1].y;
if (toSource[x1][y1]+1+toTarget[x2][y2]>len&&toSource[x2][y2]+1+toTarget[x1][y1]>len){
correct=0;
}
}此外，我是这么处理给定的墙的：设地图上每一个点都有四个方向，有一面墙就表示有两个节点的某个方向被分别阻塞了。同理边界也可以这么处理：
void solve(int x1,int y1,int x2,int y2){
for (int i=0;i<4;i++){
if (x1+dir[i][0]==x2&&y1+dir[i][1]==y2){
map[x1][y1][i]=1;
}
if (x2+dir[i][0]==x1&&y2+dir[i][1]==y1){
map[x2][y2][i]=1;
}
}
}
//防止越界
for (int i=0;i<w;i++){
map[i][0][1]=1;
map[i][h-1][0]=1;
}
for (int i=0;i<h;i++){
map[0][i][3]=1;
map[w-1][i][2]=1;
}全部代码：
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
struct node{
int x,y;
node(){
}
node(int x,int y):x(x),y(y){
}
};
//x轴是横向的
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
const char dirSt[4]={'U','D','R','L'};
int t,w,h,m,len;
int x1,x2,y1,y2;
int map[101][101][4];
int toSource[101][101];
int toTarget[101][101];
int isPath[101][101];
char path[10000];
vector<node> wall;
node target;
node q[2000];
void solve(int x1,int y1,int x2,int y2){
for (int i=0;i<4;i++){
if (x1+dir[i][0]==x2&&y1+dir[i][1]==y2){
map[x1][y1][i]=1;
}
if (x2+dir[i][0]==x1&&y2+dir[i][1]==y1){
map[x2][y2][i]=1;
}
}
}
void getPath(){
int x=0,y=0;
isPath[x][y]=1;
for (int i=0;i<len;i++){
for (int j=0;j<4;j++){
if (path[i]==dirSt[j]){
x+=dir[j][0];
y+=dir[j][1];
isPath[x][y]=1;
}
}
}
target=node(x,y);
}
void bfs(node now,int array[][101]){
node temp;
queue<node> q;
while(!q.empty()){
q.pop();
}
q.push(now);
array[now.x][now.y]=0;
while (!q.empty()){
temp=q.front();
q.pop();
for (int i=0;i<4;i++){
if (map[temp.x][temp.y][i]==0){
if (array[temp.x+dir[i][0]][temp.y+dir[i][1]]==-1){
q.push(node(temp.x+dir[i][0],temp.y+dir[i][1]));
array[temp.x+dir[i][0]][temp.y+dir[i][1]]=array[temp.x][temp.y]+1;
}
}
}
}
}
int main()
{
scanf("%d",&t);
while(t--){
int correct=1;
memset(map,0,sizeof(map));
memset(toSource,-1,sizeof(toSource));
memset(toTarget,-1,sizeof(toTarget));
memset(isPath,0,sizeof(isPath));
wall.clear();
scanf("%d%d",&w,&h);
scanf(" %s",path);
scanf("%d",&m);
len=strlen(path);
getPath();
for (int i=0;i<m;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
solve(x1,y1,x2,y2);
wall.push_back(node(x1,y1));
wall.push_back(node(x2,y2));
}
//防止越界
for (int i=0;i<w;i++){
map[i][0][1]=1;
map[i][h-1][0]=1;
}
for (int i=0;i<h;i++){
map[0][i][3]=1;
map[w-1][i][2]=1;
}
bfs(node(0,0),toSource);
bfs(target,toTarget);
for (int i=0;i<w;i++){
for (int j=0;j<h;j++){
if (isPath[i][j]==0){
if (toSource[i][j]+toTarget[i][j]<=len){
correct=0;
break;
}
}
}
if (correct==0){
break;
}
}
for (int i=0;i<wall.size()/2;i++){
if (correct==0){
break;
}
x1=wall[2*i].x;
y1=wall[2*i].y;
x2=wall[2*i+1].x;
y2=wall[2*i+1].y;
if (toSource[x1][y1]+1+toTarget[x2][y2]>len&&toSource[x2][y2]+1+toTarget[x1][y1]>len){
correct=0;
}
}
printf("%s\n",correct==1?"CORRECT":"INCORRECT");
}
return 0;
}