题意分析

本题描述了一个别墅的场景，别墅中有多个房间，房间之间有门相连，每个房间可能有控制其他房间灯的开关。布莱克先生从走廊（1号房间）出发，要在不进入黑暗房间且最后只有卧室（r号房间）灯亮的情况下到达卧室。要求编写程序找到从走廊到卧室的最短路径，其中“从一个房间移动到另一个房间”、“打开一盏灯”和“关掉一盏灯”都算作一步。

解题思路

1. 数据结构定义：
   • statusN 结构体用于表示状态，包括房间号 rNum、灯光状态 bit、步数 step 和指向下一个状态的指针 next。
   • doorN 结构体用于表示门，包括两个房间号 f 和 t，以及一个方法 getOpp 用于获取门的另一端房间号。
   • controlN 结构体用于表示开关，包括控制的房间号 hNum 和被控制的房间号 lNum。
2. 初始化：
   • 初始化 exp 数组，用于表示每个房间灯的状态值（2的幂次方）。
   • 初始化 status 数组，包含所有可能的状态（房间号和灯光状态组合）。
   • 初始化 v 数组，用于记录每个状态是否已访问。
3. BFS 搜索：
   • 从初始状态（走廊灯亮，其他灯灭）开始，使用队列进行广度优先搜索。
   • 对于当前状态，检查是否到达目标状态（卧室灯亮，其他灯灭），如果是则结束搜索。
   • 否则，尝试通过门移动到相邻房间（如果相邻房间灯亮且未访问过），或者通过开关改变当前房间灯的状态（如果有对应的开关且新状态未访问过），并将新状态加入队列。
4. 输出结果：
   • 如果找到解决方案，输出测试用例编号和最短步骤序列。
   • 如果没有找到解决方案，输出“The problem cannot be solved.”。

复杂度分析

1. 时间复杂度：
   • 初始化部分的时间复杂度主要取决于循环的次数，对于 exp 数组的初始化，循环次数为 MAX_H，时间复杂度为 $O(MAX_H)$；对于 status 数组的初始化，循环次数为 MAX_H * MAX_S，时间复杂度为 $O(MAX_H * MAX_S)$。
   • 在 BFS 搜索过程中，每个状态最多被访问一次，对于每个状态，最多需要检查 doorNum 个门和 switNum 个开关，因此时间复杂度为 $O((doorNum + switNum) * MAX_H * MAX_S)$。
   • 总体时间复杂度为 $O(MAX_H * MAX_S + (doorNum + switNum) * MAX_H * MAX_S) = O((doorNum + switNum + 1) * MAX_H * MAX_S)$。
2. 空间复杂度：
   • 主要的空间占用是 status 数组和 v 数组，它们的大小均为 (MAX_H + 2) * (MAX_S + 2)，因此空间复杂度为 $O((MAX_H + 2) * (MAX_S + 2))$。

代码实现

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX_S 1024
#define MAX_H 10
using namespace std;

struct statusN
{
    int rNum, bit, step;
    statusN *next;
}status[MAX_H + 2][MAX_S + 2];

struct doorN
{
    int f, t;
    int getOpp(int curS) //-1 not exist
    {
        if(curS == f) return t;
        else if(curS == t) return f;
        else return -1;
    }
}door[MAX_H * MAX_H + 2];

struct controlN
{
    int hNum, lNum;
}control[MAX_H * MAX_H + 2];

int v[MAX_H + 2][MAX_S + 2];
int exp[MAX_H + 2];
int roomNum, doorNum, switNum;

int getLight(int ex)
{
    for(int i = 0; i < roomNum; i++)
        if(exp[i] == ex)
            return i;
    return -1;
}

void print(statusN *cur)
{
    if(!cur->next)
        return;
    print(cur->next);

    int bitT = cur->bit, bitF = cur->next->bit, room2 = cur->rNum, room1 = cur->next->rNum;
    if(bitT == bitF)
        cout<<"- Move to room "<<room2+1<<"."<<endl;
    else
    {
        int ex = bitF ^ bitT;
        int which = getLight(ex);
        if(ex & bitT)
            cout<<"- Switch on light in room "<<getLight(ex) + 1<<"."<<endl;
        else
            cout<<"- Switch off light in room "<<getLight(ex) + 1<<"."<<endl;
    }
}

bool solve()
{
    // 将 memset 替换为循环初始化
    for (int i = 0; i < MAX_H + 2; ++i) {
        for (int j = 0; j < MAX_S + 2; ++j) {
            v[i][j] = 0;
        }
    }
    statusN *final = &status[0][exp[0]];
    final->next = NULL;
    final->step = 0;

    queue<statusN *> Q;
    v[0][exp[0]] = true;
    Q.push(final);
    bool finish = false;
    statusN *cur;

    int i;
    while(!Q.empty())
    {
        cur = Q.front();
        Q.pop();

        int bit = cur->bit, room = cur->rNum, step = cur->step;

        if(bit == exp[roomNum - 1] && room == roomNum - 1)
        {
            finish = true;
            break;
        }

        for(i = 0; i < doorNum; i++)
        {
            int opp;
            if((opp = door[i].getOpp(room))!= -1 && (bit & exp[opp]) > 0 && (!v[opp][bit]))
            {
                v[opp][bit] = 1;
                statusN *ns = &status[opp][bit];
                ns->next = cur;
                ns->step = step + 1;
                Q.push(ns);
            }
        }
        for(i = 0; i < switNum; i++)
        {
            int ctrlNum = control[i].lNum;
            if(control[i].hNum == room)
            {
                int newBit = bit ^ exp[ctrlNum];
                if(v[room][newBit])
                    continue;
                v[room][newBit] = 1;
                statusN *ns = &status[room][newBit];
                ns->next = cur;
                ns->step = step + 1;
                Q.push(ns);
            }
        }
    }
    if(!finish)
        return false;
    cout<<"The problem can be solved in "<<cur->step<<" steps:"<<endl;
    cur = &status[roomNum - 1][exp[roomNum - 1]];
    print(cur);
    return true;
}

bool compare(controlN c1, controlN c2)
{
    if(c1.hNum < c2.hNum)
        return true;
    else if(c1.hNum == c2.hNum)
    {
        if(c1.lNum <= c2.lNum)
            return true;
        return false;
    }
    return false;
}

int main()
{
    int i, j, f, t;
    exp[0] = 1;
    for(i = 1; i <= MAX_H; i++)
        exp[i] = exp[i - 1]<<1;

    for(i = 0; i < MAX_H; i++)
    {
        for(j = 0; j < MAX_S; j++)
        {
            statusN cur = {i, j, 0, NULL};
            status[i][j] = cur;
        }
    }
    int caseN = 0;
    while(cin>>roomNum>>doorNum>>switNum && (roomNum + doorNum + switNum)!= 0)
    {
        caseN++;
        for(i = 0; i < doorNum; i++)
        {
            cin>>f>>t;
            doorN cur = {f - 1, t - 1};
            door[i] = cur;
        }
        for(i = 0; i < switNum; i++)
        {
            cin>>f>>t;
            if(f == t)
            {
                switNum--;
                i--;
                continue;
            }
            controlN cur = {f - 1, t - 1};
            control[i] = cur;
        }
        cout<<"Villa #"<<caseN<<endl;
        sort(control, control + switNum, compare);
        if (!solve()) cout<<"The problem cannot be solved."<<endl;
        cout<<endl;
    }
    return 0;
}