2085：【21NOIP提高組】棋局
【題目描述】在輸了一晚上的麻將之后,，小 z 和小 c 卸掉了手機上的所有牌類游戲,。不過這怎么可能阻擋得了他們上課頹廢的決心呢,？現(xiàn)在他們的目光盯在了棋類游戲上,，但他們兩個除了天天下飛行器以外,，幾乎所有棋類游戲都只懂個大概規(guī)則,?！凹热晃覀兌紩娴荒芡嬉稽c點,，不如我們自己搞個縫合怪出來吧,！”于是,，在他們的精心腦洞之下，一個融合了圍棋,、象棋與軍棋的奇妙游戲誕生了……游戲在一張長nn行寬mm列的網(wǎng)格形棋盤上進行,，棋子落在網(wǎng)格的交叉點上。我們不妨記左上角的交叉點的坐標(biāo)為 (11,11) ,，右下角的交叉點坐標(biāo)為 (nn,mm) ,。棋子分為黑白兩色，對局雙方各執(zhí)一方棋子。每個棋子除了顏色以外還有等級,，不妨設(shè)colicoli為棋子ii的顏色,，lvilvi為棋子ii的等級。另外,，棋盤上的網(wǎng)格線共有44種狀態(tài),，對于第ii條網(wǎng)格線，設(shè)其狀態(tài)為optiopti,。輪到每方下棋時,，他可以選擇棋盤上的一個己方棋子沿網(wǎng)格線進行移動到另一個交叉點，稱為走子,。形式化定義走子的過程如下：選擇一個坐標(biāo)序列 (x0x0,y0y0),(x1x1,y1y1), ...,(xkxk,ykyk),，其中kk是任意選定的正整數(shù)，(x0x0,y0y0) 是棋子初始的位置,，(xkxk,ykyk) 是棋子最終走到的位置,，需要滿足：? 對于任意i=0,1,...,k?1i=0,1,...,k?1，坐標(biāo) (xixi,yiyi) 和 (xi+1xi+1,yi+1yi+1) 之間必須有網(wǎng)格線直接相連,，也就是說走子必須沿著網(wǎng)格線走 ,；? 對于任意ii≠jj，必須有 (xixi,yiyi) ≠(xjxj,yjyj) ,，也就是說走子過程中不能經(jīng)過重復(fù)位置，特別地 (x0x0,y0y0)≠ (xkxk,ykyk) ,，也就是說不能原地不動（或走回原地） ,。? 對于任意i=1,...,k?1i=1,...,k?1，坐標(biāo) (xixi,yiyi) 上必須沒有棋子,，也就是說走子時不能越過已有的棋子 ,。? 若 (xkxk,ykyk) 上沒有棋子，稱為普通走子,，否則稱為吃子,。在吃子過程中，設(shè)正在走的棋子顏色為col1col1,，等級為lv1lv1,，被吃的棋子顏色為col2col2，等級為lv2lv2,，則必須滿足col1col1≠col2col2,lv1lv1≥lv2lv2,，換句話說只能吃與自己顏色不同， 且等級不高于自己等級的 棋子 ,。需要注意的是,，由上述定義可以得出，不允許棋子在吃子后繼續(xù)向前走。網(wǎng)格線的狀態(tài)含義如下所述：? 如果opti=0opti=0,，代表此路不通,，走子時不能經(jīng)過這條網(wǎng)格線。? 如果opti=1opti=1,，代表這條網(wǎng)格線是一條“普通道路”,，每次走子時棋子最多只能經(jīng)過11條普通道路。? 如果opti=2opti=2,，代表這條網(wǎng)格線是一條“直行道路”,，每次走子時棋子可以經(jīng)過任意條直行道路，但只能一直沿橫向或一直沿縱向走,，不能轉(zhuǎn)彎,。如沿直行道路從(1,11,1) 經(jīng)過 (1,21,2) 走到 (1,31,3) 是可以的，但是從 (1,11,1) 經(jīng)過 (1,21,2) 走到 (2,22,2) 不行,。? 如果opti=3opti=3,，代表這條網(wǎng)格線是一條“互通道路”，每次走子時棋子可以經(jīng)過任意條互通道路,，且中途可任意轉(zhuǎn)彎,。同時規(guī)定在一次走子過程中，棋子經(jīng)過的網(wǎng)格線的狀態(tài)必須全部相同,，比如從 (1,11,1)經(jīng)過直行道路走到 (1,21,2) 再經(jīng)過互通道路走到 (1,31,3) 是不允許的,。至于如何判斷勝負(fù)等其他細(xì)節(jié)，與本題無關(guān),，故略去,。小 z 和小 c 開發(fā)出這款棋類游戲后，為了提升水平,，想了一個訓(xùn)練的策略：一開始棋盤是空的,，然后小 c 會每次往棋盤的某個空交叉點上放一枚棋子，小 z 需要快速計算出：若選擇這枚新放上的棋子進行一次走子,，棋盤上一共有多少個位置是能被走到的,？注意，因為這只是思維訓(xùn)練,，他們并不會真的走這枚棋子,。可憐的小 z 發(fā)現(xiàn)他的計算力不足以算出這個問題,，只好向你求助,。【輸入】每個測試點由多組數(shù)據(jù)組成,。第一行：一個正整數(shù)TT表示數(shù)據(jù)組數(shù),。對于每組數(shù)據(jù)：第一行：33個正整數(shù)nn,mm,qq，分別表示棋盤的行數(shù)、列數(shù)和游戲的輪數(shù),。接下來nn行,，每行為一個長m?1m?1的字符串，每個字符為0,、1,、2、30,、1,、2、3中的一個,，第ii行第jj個字符表示交叉點 (i,ji,j) 連向交叉點 (i,j+1i,j+1) 的網(wǎng)格線狀態(tài),。接下來n?1n?1行，每行為一個長mm的字符串,，每個字符為0,、1、2,、30,、1、2,、3中的一個,，第ii行第jj個字符表示交叉點 (i,ji,j) 連向交叉點 (i+1,ji+1,j) 的網(wǎng)格線狀態(tài)。接下來qq行,，每行44個非負(fù)整數(shù)coli,lvi,xi,yicoli,lvi,xi,yi,，表示在第ii輪有一枚顏色為colicoli，等級為lvilvi的棋子放在了交叉點 (xixi,yiyi) 上,。其中coli=0coli=0表示黑子，coli=1coli=1表示白子,。保證之前交叉點 (xixi,yiyi) 上沒有棋子,。【輸出】對于每組數(shù)據(jù)輸出qq行,，每行一個非負(fù)整數(shù),，表示第ii枚棋子放置后能走到的交叉點數(shù)量?！据斎霕永?3 3 51322230102330 1 2 31 2 2 11 3 1 20 2 3 21 3 2 2【輸出樣例】43332【提示】【樣例 1 解釋】放置棋子 1 后,，它能走到的位置為(2, 1),(2, 2),(3, 2),(3, 3)。放置棋子 2 后,，它能走到的位置為(2, 2),(2, 3),(3, 1),。放置棋子 3 后，它能走到的位置為(1, 1),(1, 3),(2, 2)。放置棋子 4 后,，它能走到的位置為(2, 2),(3, 1),(3, 3),。放置棋子 5 后，它能走到的位置為(2, 3),(3, 2),?！緲永?2 輸入】22 3 422331230 2 1 20 1 2 11 2 1 30 3 2 23 2 331332320 2 1 21 2 3 20 1 2 2【樣例 2 輸出】3442551【數(shù)據(jù)范圍】測試點編號n × m ≤q ≤特殊性質(zhì)1 ～ 210050無3 ～ 6500020007 ～ 82 × 105105不存在“直行道路”與“互通道路”9 ～ 11不存在“互通道路”12 ～ 14不存在“直行道路”15 ～ 16lvi= i17 ～ 18lvi= q ? i + 119 ～ 212000n, m ≤ 100022 ～ 25105無對于 100% 的數(shù)據(jù)，1≤T≤51≤T≤5,，2≤n,m≤1052≤n,m≤105,，4≤n×m≤2×1054≤n×m≤2×105，1≤q≤min1≤q≤min{105105,n×mn×m} ,，1≤lvi≤q1≤lvi≤q,，1≤xi≤n1≤xi≤n，1≤yi≤m1≤yi≤m,，colicoli∈ {00,11} ,。注：由于本題輸入輸出規(guī)模較大，建議使用較為快速的輸入輸出方式,。
直播要代碼（網(wǎng)上可找到的）,，只是貼代碼會有***，代碼較長,，轉(zhuǎn)成圖不知能否看清,。
