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