题解

8 条题解

  • 1
    @ 2010-07-27 15:59:16

    jjh好厉害!!!

  • 0
    @ 2017-10-06 22:43:41

    so water

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <iostream>  
    #include <cmath>  
    #include <cstring>  
    #include <set>  
    using namespace std;
    int ch[8][2]={{1,+1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0}};
    char a[110][110]={0};
    int lo=0;
    char word[110]={0};
    char you[8]={'D','C','B','A','H','G','F','E'};
    int e=0;
    int x_a=0,y_a=0;
    int you_a=-1;
    int n,m,w;
    bool check(int x,int y)
    {
        if(x<=0||y<=0||x>n||y>m||a[x][y]!=word[1])
            return false;
        return true;
    }
    int shen(int x,int y,int f)
    {
        int i;
        for(i=2;i<lo;i++)
        {
            x=x+ch[f][0],y=y+ch[f][1];
            if(x<=0||y<=0||x>n||y>m||a[x][y]!=word[i])
                break;
        }
        if(i==lo)
            return 1;
    }
    void check2(int x,int y,int f)
    {
        if(you_a==-1||you_a>f)
            you_a=f,x_a=x,y_a=y;
    }
    void dfs(int x,int y,int s)
    {
        
        for(int i=0;i<=7;i++)
        {
            if(check(x+ch[i][0],y+ch[i][1]))
                if(shen(x+ch[i][0],y+ch[i][1],i)==1)
                {
                    check2(x,y,i);
                    break;
                }
        }
    }
    int main()
    {
        scanf("%d %d %d",&n,&m,&w);
        for(int i=1;i<=n;i++)
        {
            char line[110]={0};
            scanf("%s",line);
            for(int j=1;j<=m;j++)
            {
                a[i][j]=line[j-1];
            }
        }
        for(int t=1;t<=w;t++)
        {
            x_a=0,y_a=0,you_a=-1;
            scanf("%s",word);
            lo=strlen(word);
            if(lo==1)
            {
                int r=0;
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=m;j++)
                        if(a[i][j]==word[0])
                        {
                            printf("%d %d D\n",i,j);
                            r=1;
                            break;
                        }
                    if(r)
                        break;
                }   
            }
            else
            {
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=m;j++)
                    {
                        if(word[0]==a[i][j])
                            e=0,dfs(i,j,0);
                    }
                }
                printf("%d %d %c\n",x_a,y_a,you[you_a]);
            }
            
        }
        return 0;
    }  
    
  • 0
    @ 2013-12-01 13:53:47

    请刚开始做这到题目的先阅读本文章,以免错误,虽然题目说只有一个能匹配,但事实不是这样的。单词的首位置是有多个的。我就是由于一开始因为这一点而折腾了四五次才过的。
    有多个首位置时a1,a2,a3……时,输出只有一个,是“最佳”的,所谓最佳是指它的最优方向在这些解中是也是最优方向,而且它的位置要行和列要尽量小(第一关键字:他的最优方向小的在前,第二关键字:行,小的在前,第三关键字:列)
    解法:
    1.首先找到第一个首字母和单词一样的位置,然后从这个位置按方向的优劣先后扩展。看是否正确。
    code
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>

    int r,c,w;
    char s[100][101];
    char word[102];
    int go[][2] = {{+1,+1},{0,+1},{-1,+1},{-1,0},{-1,-1},{0,-1},{+1,-1},{+1,0}};
    char d[10] ="DCBAHGFE";

    int main()
    {
    int i;

    void init();
    void find();

    init();
    for (i = 0;i < w;i++) {
    scanf("%s",word);
    find();
    }
    return 0;
    }

    int l,ll;
    int is_right(int x,int y,int xa,int ya)
    {
    l = strlen(word)-1;
    ll = 1;
    if ((x+xa*l < 0) || (x+xa*l >= c) || (y+ya*l < 0) || (y+ya*l >= r))
    return 0;
    while (l) {
    if (s[(y = y+ya)][(x = x+xa)] != word[ll])
    return 0;
    l--; ll++;
    }
    return 1;
    }

    void find()
    {
    int i,j,k;
    int mink,mini,minj;
    mink = 100;
    for (i = 0;i < r;i++)
    for (j = 0;j < c;j++)
    if (s[i][j] == word[0]) {
    for (k = 0;k < 8;k++)
    if (is_right(j,i,go[k][1],go[k][0])) {
    /*printf("%d %d %c\n",i+1,j+1,d[k]);
    return; 这是之前的版本,由于轻信题目描述,导致错误*/
    if (k < mink) {
    mink = k; mini = i; minj = j;
    }
    break;
    }
    }
    printf("%d %d %c\n",mini+1,minj+1,d[mink]);
    }

    void init()
    {
    int i;
    scanf("%d%d%d",&r,&c,&w);
    for (i = 0;i < r;i++)
    scanf("%s",s[i]);
    }

  • -1
    @ 2010-07-27 17:05:13

    题目描述与数据不一致,同一个字符串可能会出现多次。

    还有,要注意字符串为一个字符的情况。

  • -1
    @ 2010-07-27 16:49:16

    肥轩最傻逼

  • -1
    @ 2010-07-27 16:46:23

    CK0123傻逼

  • -1
    @ 2012-09-06 10:02:27

    只需在字母矩阵中找出这个单词的首字母的位置,便向8个方向在矩阵中寻找判断是否可以组成这个单词,如果可以,便判断是否可以更优(优先级嘛~~)

    本以为只可以过几个点,想不到AC喇.

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

  • -1
    @ 2010-07-28 03:47:43

    把原矩阵在八个方向按优先级转换成很多个字符串,然后每读一个单词按顺序KMP。

    180行!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 1

信息

ID
1707
难度
8
分类
搜索 | 枚举 点击显示
标签
(无)
递交数
770
已通过
102
通过率
13%
上传者