当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,