20xx搜索算法深入-資料下載頁
2025-07-25 15:45本頁面
【正文】 據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入 1 到 9 的數(shù)字。每個(gè)數(shù)字在每個(gè)小九宮格內(nèi)不能重復(fù)出現(xiàn)，每個(gè)數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨(dú)有一點(diǎn)和普通數(shù)獨(dú)不同，即每一個(gè)方格都有一個(gè)分值，而且如同一個(gè)靶子一樣，離中心越近則分值越高。 數(shù)獨(dú)問題 ? 每個(gè)人必須完成一個(gè)給定的數(shù)獨(dú)（每個(gè)給定數(shù)獨(dú)可能有不同的填法），而且要爭取更高的總分?jǐn)?shù)。而這個(gè)總分?jǐn)?shù)即每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的乘積的總和。游戲規(guī)定，將以總分?jǐn)?shù)的高低決出勝負(fù)。 Max=2829 7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2 思路 ? 找到一個(gè)確實(shí)有效的搜索順序，來優(yōu)化時(shí)間。 ? 每次選一個(gè)能填的數(shù)個(gè)數(shù)最小的格子進(jìn)行搜索。 ? 假設(shè)某一個(gè)格子填入了一個(gè)數(shù)字，那么它可能會(huì)對它所在的行、列、塊中其他 8個(gè)格子產(chǎn)生一次限制（即使得可填入的數(shù)的個(gè)數(shù)減少 1）。如論是否產(chǎn)生限制，我們視它為一定會(huì)產(chǎn)生一次限制，讓所有受影響的格子限制加 1。 —— 標(biāo)記限制操作 ? 首先將已給出數(shù)的格子進(jìn)行標(biāo)記限制操作。接下來，每次選出一個(gè)限制數(shù)最大并且沒有被選中的過的格子，并進(jìn)行標(biāo)記限制操作，直到所有格子都被選中為止。 ? 選擇格子的順序即為預(yù)處理得到的搜索順序。 7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2 7 9 8 9 9 10 7 9 9 8 10 11 8 6 8 7 8 8 10 11 9 7 7 10 11 11 9 11 7 6 7 7 6 7 10 11 12 11 9 10 9 11 13 11 12 12 14 13 13 11 13 3， 5， 7 3 商人的宣傳 ? Bruce在 A州成立了公司，準(zhǔn)備宣傳活動(dòng)開始后的第 L天到達(dá) B州進(jìn)行新品拍賣，期間 Bruce打算將產(chǎn)品拿到各個(gè)州去做推銷宣傳。 K國有很多個(gè)州 ,每個(gè)州都與其他一些州相鄰 ,但是 K國有規(guī)定： ? 商人只能從某些州到達(dá)另外一些州，即連通路線是單向的。 ? 商人不允許在同一個(gè)州連續(xù)宣傳兩天或以上，每天宣傳完必須離開該州。 ? 商人可以多次來到同一個(gè)州進(jìn)行宣傳。 ? 任務(wù)：算出 AB兩州之間的路線的總數(shù)。 輸入 /輸出 ? 輸入文件： 第一行包含三個(gè)整數(shù) n,m,L（ 1≤n,L≤100），表示 n個(gè)州、 m條通路， L天后必須到達(dá) B州。 接下來有 m行，每行一對整數(shù) x,y（ 1≤x,y≤n），從 x州到 y州有通路。 第 m+2行：兩個(gè)整數(shù) A,B（ 1≤A,B≤n），即 A、B州的位置。 ? 輸出文件： 一個(gè)整數(shù) t，表示從 A州到 B州滿足上述規(guī)定的路線總數(shù)。（ 2^31） 樣例 樣例數(shù)入 ? 4 5 6 ? 1 2 ? 2 3 ? 3 4 ? 4 1 ? 2 4 ? 1 4 輸出 2 1 3 2 4 思路 ? 樸素算法：寬搜 + 鄰接壓縮表 ? 遞推： t(I,L)：第 L天由別的州到達(dá) i州的路線數(shù)量 ????? ???10)1,(),(LjtLitJ?i L=0 iA L=0 i=A Thank You! ok(int x,int y) if ( (u[x1,y]) amp。amp。 (u[x+1,y]) amp。amp。 (!u[x,y1]) amp。amp。 (!u[x,y+1]) ) return 0。 if ( (!u[x1,y]) amp。amp。 (!u[x+1,y]) amp。amp。 (u[x,y1]) amp。amp。 (u[x,y+1]) ) return 0。 if ( (!u[x1,y]) amp。amp。 (!u[x,y1]) amp。amp。 (u[x1,y1]) )return 0。 if ( (!u[x+1,y]) amp。amp。 (!u[x,y1]) amp。amp。 (u[x+1,y1]) )return 0。 if ( (!u[x1,y]) amp。amp。 (!u[x,y+1]) amp。amp。 (u[x1,y+1]) )return 0。 if ( (!u[x+1,y]) amp。amp。 (!u[x,y+1]) amp。amp。 (u[x+1,y+1]) )return 0。 return 1。
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1