UVa 370 Bingo

题目描述宾果游戏是美国的一项伟大消遣方式。我们的宾果版本在一个5×55 \times 55×5的方形卡片上进行。你的任务是编写一个程序接受要放置在宾果卡片单元格中的整数。然后读取“叫号”的值可能与卡片上的数字相同也可能不同一次一个直到找到宾果或叫号结束。宾果条件满足任一即可一行中的所有五个元素都被叫到或是FREE\texttt{FREE}FREE一列中的所有五个元素都被叫到或是FREE\texttt{FREE}FREE四个角元素都被叫到或是FREE\texttt{FREE}FREE任一对角线上的五个元素都被叫到或是FREE\texttt{FREE}FREE注意卡片中值为000的格子是FREE\texttt{FREE}FREE视为已被匹配。输入格式每个测试用例的前五行每行包含五个整数0≤V≤990 \leq V \leq 990≤V≤99按从左到右的顺序填入卡片对应行。接着是一系列叫号1≤C≤991 \leq C \leq 991≤C≤99最后一行以无效的000结束。输出格式如果在叫号结束前没有找到宾果则输出No BINGO on this card.如果找到宾果则忽略后续叫号输出宾果通知然后按行升序行相同时按列升序列出所有构成宾果的格子信息行、列、值。如果同时有多个宾果按宾果类型顺序输出行优先、列优先、角优先、对角线优先中间无空行。输出格式BINGO #N R,C,V R,C,V ...样例输入1 2 3 4 5 11 12 13 14 15 21 22 0 24 25 31 32 33 34 35 91 92 93 94 95 21 22 24 25 99 0 1 2 3 4 5 11 12 13 14 15 21 22 0 24 25 31 32 33 34 35 91 92 93 94 95 99 98 97 96 0样例输出BINGO #1 3,1,21 3,2,22 3,3,FREE 3,4,24 3,5,25 No BINGO on this card.题目分析问题的本质这是一个游戏状态模拟问题。需要读取宾果卡片的5×55 \times 55×5矩阵按顺序处理叫号每次叫号后检查是否满足任一宾果条件找到宾果后输出构成该宾果的所有格子宾果条件的表示将131313种可能的宾果条件编码为行0∼40 \sim 40∼4共555种列5∼95 \sim 95∼9共555种角四个角第101010种主对角线第111111种副对角线第121212种每个格子属于多个宾果条件。例如格子(0,0)(0,0)(0,0)属于第000行第555列角条件主对角线匹配状态维护使用一个数组sum[13]记录每个宾果条件当前的“总分”。初始时每个格子有对应数值sum[cond]初始为该条件覆盖的所有格子数值之和。每次叫号后如果该号在卡片上则从对应的sum[cond]中减去该数值。当某个sum[cond] 0时表示该条件的所有格子都已被匹配或为FREE\texttt{FREE}FREE。FREE\texttt{FREE}FREE格子处理FREE\texttt{FREE}FREE格子值为000视为已匹配。在初始化时如果格子值为000则不计入sum[cond]。参考代码// Bingo// UVa ID: 370// Verdict: Accepted// Submission Date: 2016-07-08// UVa Run Time: 0.210s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintsum(13);// 每个宾果条件的当前总和vectorintoperation(25);// 当前卡片数值可能被置零vectorintbackup(25);// 原始卡片数值用于输出mapint,vectorintmapping;// 格子位置 - 所属宾果条件mapint,vectorintindexer;// 宾果条件 - 包含的格子位置mapint,vectorintlocation;// 数值 - 该数值出现的格子位置// 输出指定宾果条件的所有格子voiddisplay(){for(inti0;i13;i){if(sum[i]0){// 根据宾果类型输出标题if(i4)coutBINGO #1endl;elseif(i9)coutBINGO #2endl;elseif(i10)coutBINGO #3endl;elsecoutBINGO #4endl;for(autopos:indexer[i]){cout(pos/51),(pos%51),;if(backup[pos]0)coutFREE;elsecoutbackup[pos];coutendl;}}}}// 检查是否已宾果boolisBingo(){for(autoelement:sum)if(element0){display();returntrue;}returnfalse;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);// 预计算每个格子所属的宾果条件for(intpos0;pos25;pos){intipos/5,jpos%5;// 行条件mapping[pos].push_back(i);indexer[i].push_back(pos);// 列条件mapping[pos].push_back(j5);indexer[j5].push_back(pos);// 主对角线if(ij){mapping[pos].push_back(11);indexer[11].push_back(pos);}// 副对角线if(ij4){mapping[pos].push_back(12);indexer[12].push_back(pos);}// 四个角if((i0j0)||(i0j4)||(i4j0)||(i4j4)){mapping[pos].push_back(10);indexer[10].push_back(pos);}}intnumber,called;while(cinnumber){// 初始化fill(sum.begin(),sum.end(),0);location.clear();intreadedNumber0,row,column;do{operation[readedNumber]number;backup[readedNumber]operation[readedNumber];location[number].push_back(readedNumber);// 如果不是 FREE 格子加入各条件的和if(number!0){for(autopos:mapping[readedNumber])sum[pos]number;}readedNumber;}while(readedNumber25(cinnumber));// 检查初始状态是否已宾果理论上不会因为 FREE 格子可能凑齐一行boolignoreisBingo();// 处理叫号while(cincalled,called){if(ignore)continue;for(autolocated:location[called]){operation[located]0;for(autopos:mapping[located])sum[pos]-called;}ignoreisBingo();}if(!ignore)coutNo BINGO on this card.endlendl;elsecoutendl;}return0;}