🧠 题解分析

🚩 问题核心

我们要验证给定的墙是否满足两个要求：

给定的路径是从起点 $(0,0)$ 到终点的唯一最短路径

所有墙都是必要的（即去掉任何一个墙后，路径将不再唯一）

✅ 实现步骤

解析路径并构造目标路径坐标序列

构建图模型：每个格点是一个节点，相邻格点之间建边，除非中间被墙隔断

在去掉墙后的图上跑 BFS，验证最短路径是否唯一，并且等于给定路径

逐一移除每面墙，再重复第3步，若某面墙去掉后路径仍唯一，则该墙是冗余的 → 输出 INCORRECT

💡 总结

本题是对路径唯一性、墙构建、最短路径、冗余检测等多个图论细节的综合考察

用 BFS 检查路径唯一性是关键技巧

每一面墙都要验证其“不可或缺性”

代码实现

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
 
using namespace std;
 
#define MAXN 110
 
class Position
{
public:
    int x;
    int y;
 
    Position(){}
    Position(int x, int y):x(x), y(y){}
    ~Position(){}
};
 
class GridState
{
public:
    int x;
    int y;
    int step;
 
    GridState(){}
    GridState(int x, int y, int step = 0):x(x), y(y), step(step){}
    GridState(Position p, int step = 0):x(p.x), y(p.y), step(step){}
    ~GridState(){}
 
    bool operator==(Position &gs)
    {
        return (x==gs.x && y==gs.y);
    }
};
 
class Wall
{
public:
    int x1, y1;
    int x2, y2;
 
    Wall(){}
    Wall(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
    ~Wall(){}
};
 
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
//0->up, 1->down, 2->left, 3->right
 
bool tmap[MAXN][MAXN][4], flag;
 
string path;
 
GridState mend;
vector <Wall > walls;
 
int rows, columns;
 
int getDir(char c)
{
    switch(c){
    case 'U':return 0;
    case 'D':return 1;
    case 'L':return 2;
    case 'R':return 3;
    }
    return -1;
}
 
int getDir(int x1, int y1, int x2, int y2)
{
    //0->up, 1->down, 2->left, 3->right
    if (x1 < x2)return 3;//right
    if (x1 > x2)return 2;//left
    if (y1 < y2)return 0;//up
    if (y1 > y2)return 1;//down
    return -1;
}
 
bool isLegal(GridState tmp)
{
    return (tmp.x>=0 && tmp.x<rows && tmp.y>=0 && tmp.y<columns);
}
 
void getEndState()
{
    int x = 0, y = 0;
    for (int i = 0; i < (int)path.length(); ++i){
        int d = getDir(path[i]);
        x += dir[d][0];
        y += dir[d][1];
    }
    mend.x = x;
    mend.y = y;
    mend.step = path.length();
}
 
//--------------------Debug--------------------
 
void printMap()
{
    for (int i = columns-1; i >= 0; --i){
        for (int j = 0; j < rows; ++j){
            printf ("<");
            for (int k = 0; k < 4; ++k){
                printf (k == 0 ? "%d" : " %d", tmap[j][i][k]);
            }
            printf ("> ");
        }
        printf ("\n");
    }
}
 
void PrintChange(int d, GridState gs)
{
    if (d == 0){
        printf ("UP:\t");
    }
    else if (d == 1){
        printf ("DOWN:\t");
    }
    else if (d == 2){
        printf ("LEFT:\t");
    }
    else if (d == 3){
        printf ("RIGHT:\t");
    }
    printf ("(%d,%d)->(%d,%d)\n", gs.x-dir[d][0], gs.y-dir[d][1], gs.x, gs.y);
}
 
//--------------------Debug--------------------
 
void init()
{
    memset (tmap, true, sizeof(tmap));
    for (int i = 0; i < rows; ++i){
        tmap[i][0][1] = false;
        tmap[i][columns-1][0] = false;
    }
    for (int i = 0; i < columns; ++i){
        tmap[0][i][2] = false;
        tmap[rows-1][i][3] = false;
    }
    while (!walls.empty()){
        walls.clear();
    }
    int m;
    scanf ("%d", &m);
    int x1, y1, x2, y2;
    while (m--){
        scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
        int d = getDir(x1, y1, x2, y2);
        tmap[x1][y1][d] = false;
        tmap[x2][y2][d^1] = false;
        walls.push_back(Wall(x1, y1, x2, y2));
    }
    getEndState();
    //--------------------Debug--------------------
    //printf ("Original:\n");
    //printMap();
    //printf ("--------------------end--------------------\n");
    //--------------------Debug--------------------
}
 
int bfs(Position s, Position e)
{
    bool visited[MAXN][MAXN];
    queue <GridState > Qu;
    memset (visited, false, sizeof(visited));
    visited[s.x][s.y] = true;
    Qu.push(GridState(s, 0));
    while(!Qu.empty()){
        GridState cur = Qu.front();
        Qu.pop();
        //--------------------Debug--------------------
        //printf ("Current Poped:\t(%d,%d)\n", cur.x, cur.y);
        //--------------------Debug--------------------
        if (cur == e)return cur.step;
        for (int i = 0; i < 4; ++i){
            GridState tmp(cur.x+dir[i][0], cur.y+dir[i][1], cur.step+1);
            //--------------------Debug--------------------
            //PrintChange(i, tmp);
            //--------------------Debug--------------------
            if (isLegal(tmp) && !visited[tmp.x][tmp.y] && tmap[cur.x][cur.y][i]){
                visited[tmp.x][tmp.y] = true;
                //--------------------Debug--------------------
                //printf ("pushed:(%d, %d)\n", tmp.x, tmp.y);
                //--------------------Debug--------------------
                Qu.push(tmp);
            }
        }
    }
    return -1;
}
 
bool notOnlyOnePath()
{
    int x = 0, y = 0;
    for (int i = 0; i < (int)path.length(); ++i){
        int d = getDir(path[i]);
        int nx = x+dir[d][0], ny = y+dir[d][1];
        tmap[x][y][d] = false;
        tmap[nx][ny][d^1] = false;
        //--------------------Debug--------------------
        //printMap();
        //printf ("DELPATH::\tWall:(%d,%d)->(%d,%d)\n", x, y, nx, ny);
        //--------------------Debug--------------------
        int pathLength = bfs(Position(0, 0), Position(mend.x, mend.y));
        //--------------------Debug--------------------
        //printf ("O~D-:>%d\n", pathLength);
        //--------------------Debug--------------------
        tmap[x][y][d] = true;
        tmap[nx][ny][d^1] = true;
        x = nx, y = ny;
        if (pathLength != -1 && pathLength <= mend.step)return true;
    }
    return false;
}
 
bool deleteWall()
{
    for (int i = 0; i < (int)walls.size(); ++i){
        Position first(walls[i].x1, walls[i].y1);
        Position second(walls[i].x2, walls[i].y2);
        int d = getDir(first.x, first.y, second.x, second.y);
        tmap[first.x][first.y][d] = true;
        tmap[second.x][second.y][d^1] = true;
        //--------------------Debug--------------------
        //printMap();
        //printf ("DELWALL::\tROAD:(%d,%d)->(%d,%d)\n", first.x, first.y, second.x, second.y);
        //--------------------Debug--------------------
        int pathLength = bfs(Position(0, 0), Position(mend.x, mend.y));
        //--------------------Debug--------------------
        //printf ("O~D:\t%d\n", pathLength);
        //--------------------Debug--------------------
        if (pathLength >= mend.step && !notOnlyOnePath()){
            tmap[first.x][first.y][d] = false;
            tmap[second.x][second.y][d^1] = false;
            return true;
        }
        tmap[first.x][first.y][d] = false;
        tmap[second.x][second.y][d^1] = false;
    }
    return false;
}
 
void solve()
{
    flag = true;
    int pathLength = bfs(Position(0, 0), Position(mend.x, mend.y));
    //--------------------Debug--------------------
    //printf ("ORI::\tO~D-:>%d\n", pathLength);
    //--------------------Debug--------------------
    if (pathLength != mend.step){
        flag =false;
    }
    if (flag && notOnlyOnePath()){
        flag = false;
    }
    if (flag && deleteWall()){
        flag = false;
    }
    if (flag){
        puts("CORRECT");
    }
    else {
        puts("INCORRECT");
    }
}
 
int main()
{
    //--------------------Debug--------------------
    //freopen("out.dat", "w", stdout);
    //freopen("in.dat", "r", stdin);
    //--------------------Debug--------------------
    int t, iCase = 1;
    scanf ("%d", &t);
    while (t--){
        scanf ("%d%d", &rows, &columns);
        cin >> path;
        init();
        //--------------------Debug--------------------
        //printf ("Case:%d\n", iCase++);
        //--------------------Debug--------------------
        solve();
    }
    //--------------------Debug--------------------
    //fclose(stdin);
    //fclose(stdout);
    //--------------------Debug--------------------
    return 0;
}