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