[cpp]
/**这里采用暴力法，首先将所有大写字母转化为小写，然后遍历整个矩阵，
?*搜索8个方向，获得搜索到的字符串，然后与目标字符串
?*对比，如果搜索到的字符串前面包含目标字符串，则找到该串，输出位置
?*/?
#include ?
#include ?
#include ?
#include ?
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 ??????????? if(s[i]!=all[i])?
??????????????? return 0;?
??? }?
??? return 1;?
}?
?
//遍历每个位置?
void findPos(const char *s, int row, int col){?
??? for(int i=0; i ??????? for(int j=0; j ??????????? for(int l=0; 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 ??????????? scanf("%s",&map[i]);?
??????????? for(int j=0; j ??????????????? if(isupper(map[i][j])) map[i][j] += 32;?
??????? }? www.2cto.com
??????? scanf("%d",&ans_num);?
??????? getchar();?
??????? for(int i=0; i ??????????? gets(street[i]);?
??????????? for(int j=0; j ??????????????? if(isupper(street[i][j])) street[i][j] += 32;?
??????? }?
??????? for(int i=0; i ??????????? findPos(street[i], row, col);?
??????? }?
??? }?
??? return 0;?
}?
|