题解 P1076 【寻宝】

Dark_Archon · 2017-07-07 19:26:55 · 题解

这段代码应该是挺易懂的代码吧...

这道题整体感觉坑很多，代码却不那么复杂。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxfloor=10001;
const int maxroom=101;

int n,m;
int startroom;

struct room_info
{
    bool up;
    int sign;
};
room_info rooms[maxfloor][maxroom];
int floorstair[maxfloor];//这是优化，每一层有几个楼梯

int floor(int floornum,int s)//floor()模拟层数 floornum当前层 s开始房间
{
    if(floornum==n+1) return 0;//询问密钥
    int cnt=0;//计算一共有多少个有楼梯的房间
    int nowroom=s;
    int want=rooms[floornum][s].sign;
    want=want%(floorstair[floornum]);
    if(want==0)//特判want==0，节省时间
    {
        want=floorstair[floornum];//数学环形植树，一大坑题(第一次WA在这里了)
    }
    while(true)
    {
        if(rooms[floornum][nowroom].up==1)//有楼梯的房间
            ++cnt;
        if(cnt==want)//这是第m个有楼梯的房间
        {
            return (floor(floornum+1,nowroom)+rooms[floornum][s].sign)%20123;//返回密钥
        }
        ++nowroom;//下一个房间
        if(nowroom==m) nowroom=0;//从零开始，一大坑题
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<m;++j)
        {
            scanf("%d%d",&rooms[i][j].up,&rooms[i][j].sign);
            floorstair[i]+=rooms[i][j].up;
        }
    }
    scanf("%d",&startroom);
    printf("%d\n",floor(1,startroom));
    return 0;
}

另外，floor是cmath库的关键字，我编完之后才想起来...