題目
| 試題描述 |
| 傳說很遙遠的藏寶樓頂層藏著誘人的寶藏。 小明歷盡千辛萬苦終于找到傳說中的這個藏寶樓，藏寶樓的門口豎著一個木板，上面寫有幾個大字：尋寶說明書。 ??? 說明書的內容如下：藏寶樓共有N+1層，最上面一層是頂層，頂層有一個房間里面藏著寶藏。除了頂層外，藏寶樓另有 N層，每層M個房間，這M個房間圍成一圈并按逆時針方向依次編號為0，…，M-1。其中一些房間有通往上一層的樓梯，每層樓的樓梯設計可能不同。每個房間里有一個指示牌，指示牌上有一個數字x，表示從這個房間開始按逆時針方向選擇第x個有樓梯的房間（假定該房間的編號為k），從該房間上樓，上樓后到達上一層的k號房間。比如當前房間的指示牌上寫著2，則按逆時針方向開始嘗試，找到第2個有樓梯的房間，從該房間上樓。如果當前房間本身就有樓梯通向上層，該房間作為第一個有樓梯的房間。尋寶說明書的最后用紅色大號字體寫著：“尋寶須知：幫助你找到每層上樓房間的指示牌上的數字（即每層第一個進入的房間內指示牌上的數字）總和為打開寶箱的密鑰”。請幫助小明算出這個打開寶箱的密鑰。 |
| 輸入 |
| 第一行2個整數N和M，之間用一個空格隔開。N表示除了頂層外藏寶樓共N層樓，M表示除頂層外每層樓有M個房間。接下來N*M行，每行兩個整數，之間用一個空格隔開，每行描述一個房間內的情況，其中第(i-1)*M+j?行表示第i層j-1號房間的情況（i=1,2,…,N；j=1,2,…,M）。第一個整數表示該房間是否有樓梯通往上一層（0表示沒有，1表示有），第二個整數表示指示牌上的數字。注意，從j號房間的樓梯爬到上一層到達的房間一定也是j號房間。最后一行，一個整數，表示小明從藏寶樓底層的幾號房間進入開始尋寶（注：房間編號從0開始）。 |
| 輸出 |
| 輸出只有一行，一個整數，表示打開寶箱的密鑰，這個數可能會很大，請輸出對20123取模的結果即可。 |
| 輸入示例 |
| 2?3 1?2 0?3 1?4 0?1 1?5 1?2 1 |
| 輸出示例 |
| 5 |
| 其他說明 |
| 【輸入輸出樣例說明】 ????第一層： ????????0?號房間，有樓梯通往上層，指示牌上的數字是?2；? ????????1?號房間，無樓梯通往上層，指示牌上的數字是?3； ????????2?號房間，有樓梯通往上層，指示牌上的數字是?4； ????第二層： ????????0?號房間，無樓梯通往上層，指示牌上的數字是?1； ????????1?號房間，有樓梯通往上層，指示牌上的數字是?5； ????????2?號房間，有樓梯通往上層，指示牌上的數字是?2； 小明首先進入第一層（底層）的?1?號房間，記下指示牌上的數字為3，然后從這個房間開始，?沿逆時針方向選擇第3個有樓梯的房間2號房間進入，上樓后到達第二層的2號房間，記下指示牌上的數字為2，?由于當前房間本身有樓梯通向上層，該房間作為第一個有樓梯的房間。因此，此時沿逆時針方向選擇第2個有樓梯的房間即為1號房間，進入后上樓梯到達頂層。這時把上述記下的指示牌上的數字加起來，即3+2=5，所以打開寶箱的密鑰就是5。 【數據范圍】0<N≤10000，0<M≤100，0<x≤1,000,000。 |
分析
這道題是一個裸的模擬，但有許多細節需要注意。我們定義f[x][y]表示第x層第y個房間是否有樓梯，num[x][y]表示第x層第y個房間指示牌上的數字。sum[i]表示第i層有幾個有樓梯的房間。然后逐層模擬，找有樓梯的房間。這部很關鍵，代碼如下。
if(f[floar][room]) room_num--; //room_num表示還需要找幾個有樓梯的房間。
room_num=((room_num-1)%sum[floar])+1; //括號里減1最后加1保證值不為0，因為(room_num-1)%sum[floar]≥0且1＞0。最后化簡得：若(room_num-1)%sum[floar]=0，整體為1。反之為1。?
while(room_num>0)
{room++;if(room>m) room=0; //若搜到最高房間號，從0開始。實現一個循還。if(f[floar][room]) room_num--; //若f[floar][room]為1，說明這個有樓梯。則還需要找的有樓梯的房間數--。}
再定義ans，把每層第一個有樓梯的房間指示牌上的數字累加。值得注意的是，房間號是從0到m-1。完整代碼如下。
#include <bits/stdc++.h>
using namespace roomd;
#define MOD 20123
int n,m,num[10005][105],sum[10005],ans,room,floar=1;
bool f[10005][105];
int main() {scanf("%d %d",&n,&m);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {int x,y;scanf("%d %d",&x,&y);if(x) {f[i][j]=true;sum[i]++;}num[i][j]=y;}}scanf("%d",&room);room++;while(floar<=n) {int room_num=num[floar][room];ans=(ans+room_num)%MOD;if(f[floar][room]) room_num--;room_num=((room_num-1)%sum[floar])+1; //括號里減1最后加1保證值不為0，因為(room_num-1)%sum[floar]≥0且1＞0。最后化簡得：若(room_num-1)%sum[floar]=0，整體為1。反之為1。while(room_num>0) {room++;if(room>m) room=0;if(f[floar][room]) room_num--;}floar++;}printf("%d",ans);return 0;
}
)
