國家集訓隊作業(yè)ural競賽

1、題目來源ural 1603 Erudite題目描述判斷一個字符串在 4*4 的表格中是否存在.算法將所有字符串一一放入表格中檢驗是否存在.算法證明無需證明算法實現(xiàn)在表格中找到首字母,向四周擴展,看看字符串能否存在.源代碼const dx:Array1.5of long=(0,0,1,-1,0);dy:Array1.5of long=(1,-1,0,0,0);var st:array1.4of string4; ss:string; f:Array1.4,1.4of;flag: i,j,k,n:long ch:char;s,t:Arraya.zof long;function check(x,y

2、,k:long):;var i:long begin fx,y:=true;if k=length(ss) then exit(true); for i:=1 to 4 doif (x+dxi) in 1.4 thenif (y+dyi) in 1.4 thenif not fx+dxi,y+dyi or (i=5) then if stx+dxi,y+dyi=ssk+1 thenif check(x+dxi,y+dyi,k+1) then exit(true); fx,y:=false;exit(false);end;beginfor i:=1 to 4 do readln(sti); fo

3、r i:=1 to 4 dofor j:=1 to 4 do inc(ssti,j); readln(n);for i:=1 to n do begin readln(ss);fillchar(t,sizeof(t),0);for j:=1 to length(ss) flag:=true;nc(tssj);for ch:=a to z if not flag then beginwrin(ss,: NO); continue;end;f schtch then begin flag:=false; break; end;fillchar(f,sizeof(f),0); for j:=1 to

4、 4 dobeginfor k:=1 to 4 doif stj,k=ss1 thenif check(j,k,1) then begin flag:=false; break; end; if not flag then break;end;if not flag then wrin(ss,: YES) else wrin(ss,: NO);end; end.原題描述：1603. EruditeTime Limit: 1.0 second Memory Limit: 64 MBPetr likes found in a table 4 to solve crossword puzzles a

5、nd other conundrums. Once henewspr a new puzzle called Erudite. There was a square4 filled with letters. It was required to findhe tableas to nomany words assible; thewords could go up, down, to the right, or angles any number of times but they couldthe left and break at rightve self-ersections.Petr

6、s friend Vasya told himt it wasvery silly to spend time easier to write a program dictionary. Petr was offended write the program yourself. Isolving this puzzle. He told it was much would search for the required words in atand told Vasya: If you aret clever,will cope with the puzzle myself, the way

7、I like. Help Vasya to get out of the situation. You should write this program.InputThefour lines of the inpontain a table 4 4consisting ofnumber n (n he followinglowercase English100) of wordsletters.he next line there is thehe dictionary. per line. EachThese words are givenn lines,ordword consists of lowercase English 16.letters and has length from 1 toOutputFor each word from the dictionary output YES if this word can be foundhe table and NO otherwise. Use the format givenhe sample.Sampleinputoutputabra adac babr arcaabracadabra: YES ababaab: YES abab