uva_10010-Where's Waldorf?
[cpp]/**这里采用暴力法,首先将所有大写字母转化为小写,然后遍历整个矩阵,
*搜索8个方向,获得搜索到的字符串,然后与目标字符串
*对比,如果搜索到的字符串前面包含目标字符串,则找到该串,输出位置
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define MAX 200
#define DIR 8
char map[MAX][MAX];
char street[MAX][MAX];
char all[MAX];
int dir[][2]={{0,-1}, {1,-1}, {1,0}, {1,1},
{0,1}, {-1,-1}, {-1,0}, {-1,1}};
//找到每一组字符串
char *findAll(int row, int col, int max_row, int max_col, int d){
int tmp_x, tmp_y, tmp_row, tmp_col, n(0);
all[n++] = map[row][col];
tmp_row = row; tmp_col = col;
tmp_x = 0; tmp_y = 0;
do{
tmp_x += dir[d][0]; tmp_y += dir[d][1];
tmp_row = row + tmp_x; tmp_col = col + tmp_y;
if(tmp_row >= 0 && tmp_row < max_row && tmp_col >= 0 && tmp_col < max_col)
all[n++] = map[tmp_row][tmp_col];
}while(tmp_row >= 0 && tmp_row < max_row && tmp_col >= 0 && tmp_col < max_col);
all[n] = '\0';
return all;
}
//比较目标串是否是找到字符串的子串
int findstreet(const char *s, char *all){
for(int i=0; i<strlen(s); i++){
if(s[i]!=all[i])
return 0;
}
return 1;
}
//遍历每个位置
void findPos(const char *s, int row, int col){
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
for(int l=0; l<DIR; l++){
char *all = findAll(i,j,row,col,l);
if(findstreet(s,all)){
printf("%d %d\n",i+1,j+1);
return ;
}
}
}
}
}
int main(int argc, char const *argv[])
{
int cas, row, col, ans_num;
scanf("%d",&cas);
while(cas--){
scanf("%d %d",&row,&col);
for(int i=0; i<row; i++){
scanf("%s",&map[i]);
for(int j=0; j<strlen(map[i]); j++)
if(isupper(map[i][j])) map[i][j] += 32;
} www.zzzyk.com
scanf("%d",&ans_num);
getchar();
for(int i=0; i<ans_num; i++){
gets(street[i]);
for(int j=0; j<strlen(street[i]); j++)
if(isupper(street[i][j])) street[i][j] += 32;
}
for(int i=0; i<ans_num; i++){
findPos(street[i], row, col);
}
}
return 0;
}
补充:软件开发 , C++ ,