發(fā)一下牢騷和主題無(wú)關(guān)：
????
| ? ?Where's Waldorf?? |
????Given a?
????m
?by?
????n
?grid of letters, (?
????
????), and a list of words, find the location in the grid at which the word can be found. A word matches a straight, uninterrupted line of letters in the grid. A word can match the letters in the grid regardless of case (i.e. upper and lower case letters are to be treated as the same). The matching can be done in any of the eight directions either horizontally, vertically or diagonally through the grid.
????
Input?
????The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
????The input begins with a pair of integers,? m ?followed by? n ,??in decimal notation on a single line. The next? m ?lines contain? n ?letters each; this is the grid of letters in which the words of the list must be found. The letters in the grid may be in upper or lower case. Following the grid of letters, another integer? k ?appears on a line by itself (?). The next? k ?lines of input contain the list of words to search for, one word per line. These words may contain upper and lower case letters only (no spaces, hyphens or other non-alphabetic characters).
????
Output?
????For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
????For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output. The integers must be separated by a single space. The first integer is the line in the grid where the first letter of the given word can be found (1 represents the topmost line in the grid, and? m ?represents the bottommost line). The second integer is the column in the grid where the first letter of the given word can be found (1 represents the leftmost column in the grid, and? n ?represents the rightmost column in the grid). If a word can be found more than once in the grid, then the location which is output should correspond to the uppermost occurence of the word (i.e. the occurence which places the first letter of the word closest to the top of the grid). If two or more words are uppermost, the output should correspond to the leftmost of these occurences. All words can be found at least once in the grid.
????
Sample Input?
1
8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert
????
Sample Output?
2 5
2 3
1 2
7 8
????
????
????
?????
????Miguel Revilla?
????2000-08-22
????
????
????【粗心】：
????輸入：
????給你一個(gè)由字母成組的網(wǎng)格，M行N列。找尋一個(gè)單詞在網(wǎng)格中的置位。 一個(gè)單詞匹配網(wǎng)格中聯(lián)系不間斷的字母。可以沿意任方向匹配，一共可以匹配八個(gè)方向。略忽大小寫(xiě)。
???? 須要匹配的字符串有 K 個(gè)。
???? 出輸：
???? 每組出輸之間都一行空行。
???? m n ： m 代表匹配的最上面的行
???? ????? n 代表匹配的最下面的行
???? 如果結(jié)果有多個(gè)，只出輸匹配串。要求：匹配串的第一個(gè)字母必須是最高最左的。結(jié)果至少有一個(gè)。
????【代碼】：
/*********************************
* 期日：2013-4-23
* 作者：SJF0115
* 題號(hào): 標(biāo)題10010 - Where's Waldorf?
* 起源：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=951
* 結(jié)果：AC
* 起源：UVA
* 結(jié)總：
**********************************/
#include<stdio.h>
#include<string.h>
char Matrix[51][51];
char str[21],temp[21];
int StartR,StartC;
//M行 N列
int Match(int M,int N,int &StartR,int &StartC){
int i,j,k,flag;
StartR = 51,StartC = 51;
int len = strlen(str);
for(i = 0;i < M;i++){
for(j = 0;j < N;j++){
flag = 1;
//left - right
if(j + len <= N){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i][j+k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//right - left
if(j - len + 1>= 0){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i][j-k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//up - down
if(i + len <= M){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i+k][j]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//down - up
if(i - len + 1 >= 0){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i-k][j]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//right - up
if(j + len <= N && i - len + 1 >= 0){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i-k][j+k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//right - down
if(j + len <= N && i + len <= M){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i+k][j+k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//left - up
if(j - len + 1 >= 0 && i - len + 1 >= 0){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i-k][j-k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
//left - down
if(j - len + 1 >= 0 && i + len <= M){
flag = 0;
for(k = 0;k < len;k++){
if(str[k] != Matrix[i-k][j+k]){
flag = 1;
break;
}
}
if(flag == 0){
if(StartR > i+1){
StartR = i+1;
StartC = j+1;
}
else if(StartR == i+1 && StartC > j+1){
StartR = i+1;
StartC = j+1;
}
}
}
}//for j
}//for i
return 0;
}
int main (){
int i,j,Case,k,M,N;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&Case) != EOF){
while(Case--){
scanf("%d %d",&M,&N);
//輸入字符陣矩
for(i = 0;i < M;i++){
scanf("%s",temp);
for(j = 0;j < N;j++){
Matrix[i][j] = temp[j];
//轉(zhuǎn)換為小寫(xiě)
if(Matrix[i][j] >= 'A' && Matrix[i][j] <= 'Z'){
Matrix[i][j] = Matrix[i][j] - 'A' + 'a';
}
}
}
scanf("%d",&k);
//待匹配串
for(i = 0;i < k;i++){
scanf("%s",str);
int len = strlen(str);
//轉(zhuǎn)換為小寫(xiě)
for(j = 0;j < len;j++){
if(str[j] >= 'A' && str[j] <= 'Z'){
str[j] = str[j] - 'A' + 'a';
}
}
//printf("%s",str);
Match(M,N,StartR,StartC);
printf("%d %d\n",StartR,StartC);
}
//每組測(cè)試之間有空行
if(Case){
printf("\n");
}
}
}
return 0;
}
文章結(jié)束給大家分享下程序員的一些笑話語(yǔ)錄： 《諾基亞投資手機(jī)瀏覽器UCWEB，資金不詳或控股》杯具了，好不容易養(yǎng)大的閨女嫁外國(guó)。（心疼是你養(yǎng)的嗎？中國(guó)創(chuàng)業(yè)型公司創(chuàng)業(yè)初期哪個(gè)從國(guó)有銀行貸到過(guò)錢(qián)？）
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
