[計(jì)算機(jī)]猜圖游戲解題報(bào)告-wenkub
2023-04-26 22:27:27 本頁面
【正文】 然，這完全符合上述“簡(jiǎn)單推理”的定義：僅考慮某一行（列）的信息以及該行（列）中已知的方塊的顏色，推理出該行（列）中更多方塊的顏色。建立一個(gè)隊(duì)列，將這些已經(jīng)確定的格子加入這個(gè)隊(duì)列，然后進(jìn)行如下的操作。至此，深搜的算法已經(jīng)大體完成，基本上20*20的數(shù)據(jù)可以秒殺并且輸出所有解，暫時(shí)因?yàn)闆]有30*30的數(shù)據(jù)來進(jìn)行極限測(cè)試，但是由于題述中說是保證唯一解，因此應(yīng)該能夠在時(shí)限內(nèi)得到這一組解。當(dāng)然，在這里也可以搜索黑格，但是搜索空當(dāng)?shù)膬?yōu)勢(shì)在于我們可以在每一行之前和之后都添加一個(gè)白格，這樣就可以確定空當(dāng)?shù)拈_始和結(jié)束，而黑格就無法這樣做了。顯然，每一列所要求的數(shù)字排列是有序的，那么，對(duì)于每一列我們都可以用兩個(gè)數(shù)字M，N來表示當(dāng)前該列的狀態(tài)，即已經(jīng)判斷了該列的前M個(gè)數(shù)，并且第M+1個(gè)數(shù)已經(jīng)檢查了N格（顯然N是小于第M+1個(gè)數(shù)的）。因?yàn)檫@個(gè)表中有三種狀態(tài)：填0（代表白格），填1（代表黑格），以及填1（代表未確定）。（“簡(jiǎn)單推理”的定義為，僅考慮某一行（列）的信息以及該行（列）中已知的方塊的顏色，推理出該行（列）中更多方塊的顏色。作者聲明：此題所附程序，深搜是正確的，會(huì)輸出所有解。）【算法分析】盡管一開始就看到了簡(jiǎn)單推理這句話，但是一開始并沒有想到有效利用這一條件的方法，于是先考慮到用深搜的做法，配合強(qiáng)剪枝來解決。在一開始考慮的時(shí)候，我先把所有已經(jīng)確定的行和列都填好，因此就必須把1和0區(qū)別開來，但是為了接替方便，最后還是將這些已經(jīng)確定的行作為搜索時(shí)的小剪枝，而避免了1和0的區(qū)分，因此，表的狀態(tài)就只要用一個(gè)布爾數(shù)組來判斷一下就行了。如果當(dāng)前我們判斷這一格是白格，那么判斷之前的狀態(tài)中N是否等于第M+1個(gè)數(shù)，如果等于，則M加上1，N歸零，否則如果小于，則顯然不可行，回溯；如果當(dāng)前我們判斷這一個(gè)是黑格，那么判斷之前的狀態(tài)中N+1是否超過第M+1個(gè)數(shù)，如果超過，那么不可行，如果不超過，那么N加上1；當(dāng)判斷完整張表之后，相當(dāng)于在整張表之下全部添加一列白格，在對(duì)每一列進(jìn)行判斷。搜索空當(dāng)之后，將空當(dāng)中的每一個(gè)白格都進(jìn)行一次判斷，然后對(duì)這個(gè)空檔之后的一段黑格再逐個(gè)進(jìn)行判斷。經(jīng)過與張若愚的討論和借鑒，我又重新開始研究了簡(jiǎn)單推理的辦法。首先是預(yù)處理，對(duì)于每一行（或列），我們可以算出所有它可能有的排列。而且，如果是做為手工筆算小數(shù)據(jù)的方法，顯然是很好的（尤其是這種描述很符合思維習(xí)慣）。這樣，我們就可以很輕松的判斷某一個(gè)是否在所有排列中保持同樣的性質(zhì)了：如果黑格表中某一列的Head直接指向NIL，則這一列必然都是代表白格，反之，白格表中同樣的情況下，這一列必然都是代表黑格?！拘牡皿w會(huì)】這道題是我最先開始研究的一道題，也許是因?yàn)槲以?jīng)玩過這個(gè)游戲的緣故吧。 【附錄】 2006選拔賽第三輪第一試 猜圖游戲 輸入文件名： 時(shí)間限制：2S 輸出文件名：【題目描述】 有一個(gè)游戲是這樣的。 可以保證的是在符合這些條件的情況下，答案的圖畫是唯一確定的。（圖中白色方塊表示未知的方塊，中間有點(diǎn)的方塊以及全黑的方塊分別表示推理出一定是白色或黑色的方塊）。其中Si為第i行中連續(xù)的黑方塊的組數(shù)。其中Ti為第i列中連續(xù)的黑方塊的組數(shù)。其中，用連續(xù)的兩個(gè)號(hào)表示黑方塊，用連續(xù)的兩個(gè)點(diǎn)表示白方塊。 node=record ch:array[0..1]of point。 c,d,s:array[0..maxm]of longint。 n,m:longint。 p,q:point。 for i:=1 to m do begin u:=ord(f[i])。 q^.f:=p。 end。 build(flag,t+1,i+c[t]+1,resc[t]1)。var i,j,k,l:longint。 a[i]^.ch[1]:=nil。 for j:=1 to c[0] do begin read(c[j])。 end。 end。var i,j:longint。,tt,39。 for i:=1 to n do b1[i]:=b[i]。 for i:=1 to n do begin for j:=1 to m do if ans[i,j] then write(39。)。 for i:=1 to n do b[i]:=b1[i]。 able:boolean。 close(output)。 for i:=1 to t[flag,0] do for j:=u[flag,i] to u[flag,i]+t[flag,i]1 do f[j]:=true。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1