hihocoder #1094 : Lost in the City微软苏州校招笔试 12月27日 (建图不大【暴力枚举】 子图的4种形态 1Y )

By | 01月30日
Advertisement

#1094 : Lost in the City

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Little Hi gets lost in the city. He does not know where he is. He does not know which direction is north.

Fortunately, Little Hi has a map of the city. The map can be considered as a grid of N*M blocks. Each block is numbered by a pair of integers. The block at the north-west corner is (1, 1) and the one at the south-east corner is (N, M). Each block is represented by a character, describing the construction on that block: '.' for empty area, 'P' for parks, 'H' for houses, 'S' for streets, 'M' for malls, 'G' for government buildings, 'T' for trees and etc.

Given the blocks of 3*3 area that surrounding Little Hi(Little Hi is at the middle block of the 3*3 area), please find out the position of him. Note that Little Hi is disoriented, the upper side of the surrounding area may be actually north side, south side, east side or west side.

输入

Line 1: two integers, N and M(3 <= N, M <= 200).
Line 2~N+1: each line contains M characters, describing the city's map. The characters can only be 'A'-'Z' or '.'.
Line N+2~N+4: each line 3 characters, describing the area surrounding Little Hi.

输出

Line 1~K: each line contains 2 integers X and Y, indicating that block (X, Y) may be Little Hi's position. If there are multiple possible blocks, output them from north to south, west to east.

样例输入
8 8
...HSH..
...HSM..
...HST..
...HSPP.
PPGHSPPT
PPSSSSSS
..MMSHHH
..MMSH..
SSS
SHG
SH.
样例输出
5 4

算法分析:在大地图中找子地图,注意:子地图的方向不确定,也就是说,子地图可以旋转4次90度,产生4中形态。只要大地图中,有其中任意一种形态,那个位置就是合法的。找出所有这样的状态。一开始我想把子地图存储成二维数组,后来发现要把它变换成共4中形态,变换的语句描述很是麻烦,修饰语法就得写一大堆。为了一下xu建哥有什么好的策略:可以把子图存储成一维数组。然后按照四中形态的遍历顺序去大地图中进行遍历。看看在当前的i,j,能不能遍历出这样的序列,如果能就说明这个位置合法,直接输出。否则继续枚举寻找。代码:
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>

using namespace std;

char ch[202][202];
char c[11];

bool test_ok(int dd, int ff)
{
    int i, j;
    int k=0;
    int ok=1;
    for(i=dd; i<=dd+2; i++)
    {
        for(j=ff; j<=ff+2; j++)
        {
            if(ch[i][j]==c[k])
            {
                k++;
            }
            else
            {
                ok=0; break;
            }
        }
        if(ok==0)
            break;
    }
    if(ok==1)
    {
        return true;
    }
    ok=1; k=0;
    for(j=ff; j<=ff+2; j++)
    {
        for(i=dd+2; i>=dd; i--)
        {
            if(ch[i][j]==c[k])
                k++;
            else
            {
                ok=0; break;
            }
        }
        if(ok==0)
            break;
    }
    if(ok==1)
        return true;

    ok=1; k=0;
    for(i=dd+2; i>=dd; i--)
    {
        for(j=ff+2; j>=ff; j--)
        {
            if(ch[i][j]==c[k])
                k++;
            else
            {
                ok=0; break;
            }
        }
        if(ok==0)
            break;
    }
    if(ok==1)
        return true;

    ok=1; k=0;
    for(j=ff+2; j>=ff; j--)
    {
        for(i=dd; i<=dd+2; i++)
        {
            if(ch[i][j]==c[k])
                k++;
            else
            {
                ok=0; break;
            }
        }
        if(ok==0)
            break;
    }
    if(ok==1)
        return true;

    return false;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int i, j;
    char cc;
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cc=getchar();
            while(!isalpha(cc)&&cc!='.' ) //不是字母且不是.
            {
                cc=getchar();
            }
            ch[i][j]=cc;
        }
    } //建立地图
    int e=0;
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
        {
            cc=getchar();
            while(!isalpha(cc)&&cc!='.')
                cc=getchar();
            c[e++]=cc;
        }
    c[e]='\0';
    //printf("%s", c);
    //建立小地图
    for(i=0; i<=n-3; i++)
    {
        for(j=0; j<=m-3; j++)
        {
            if(test_ok(i, j))
            {
                printf("%d %d\n", i+1+1, j+1+1);
            }
        }
    }
    return 0;
}

Similar Posts:

  • 微软苏州校招笔试 12月27日

    题目1 : Lost in the City 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Little Hi gets lost in the city. He does not know where he is. He does not know which direction is north. Fortunately, Little Hi has a map of the city. The map can be considered as a grid

  • [新闻] 20111214,微软12月14日发布13个安全补丁

    大家好,我是 Richard Chen. 微软于北京时间12月14日清晨发布13个安全补丁,其中3个为最高级别严重等级,其余10个均为重要等级,共修复了 Microsoft Windows, Office, Internet Explorer, Microsoft Publisher 和 Windows Media Player 中的19个安全漏洞.请大家根据补丁严重性程度.利用指数和自身环境综合考量部署顺序.请特别优先部署 MS11-092 和 MS11-087.MS11-092 修复了 Wi

  • 微软透露Vista发布日期 12月5日

    微软透露说,今年12月5日是公司新一代Vista操作系统的正式发布日期. 本周四在伦敦举行的一次会议上微软公司Windows客户销售专业人员DavidHipwell透露了公司的发布计划,他在一份声明中说:"我们将在12月5日正式发布Vista.Office 2007 和Exchange 2007 . " 微软最初敲定Vista的发布时间是今年第四季度,修订后的估计推出时间是明年一月份,周四的声明强调了正式发布日期将在圣诞节之前.企业版Vista预期仍然在今年十一月份推出.家庭基本版和家

  • [国际资讯]“黑屏计划”证实了微软OS存在后门 10月20日

    据微软内部邮件显示,10月20日微软将在中国再次对盗版WindowsXP进行打击,并首次对盗版Office进行验证,盗版用户的Windows XP及Office将被强制插入多出明显的提醒标识.微软通知称未通过正版验证的Windows XP将黑屏. 如果微软的"黑屏计划"不是空穴来风,我不知道10月20日那天中国将会有多少电脑将出现黑屏.可我知道我周围有很多人的电脑肯定会黑屏,而且会不断地收到来自微软的提示. 腾讯网针对此事的一项9万多人的调查显示,84%的人使用的是盗版,83.6%的人

  • 【hihocoder】1237 : Farthest Point -&amp;gt;微软2016校招在线笔试题

    注意以圆点靠左,x的坐标轴 需要用ceil,向前进位 以圆点靠右,x的坐标要用floor 以圆点靠上,y的坐标要用floor 以圆点靠下,y的坐标要用ceil 同时由于要输出x最大,x弱相等,y最大,所以从x最大开始遍历,避免大量比较 /** * @author johnsondu * @time 19:30 14th Oct 2015 * @status Accepted * @strategy simple calculate using x^2 + y^2 = r^2 * calculat

  • 2014年12月6~12月7日,杨学明老师《软件测试管理及调优实务》内训在苏州某网络企业成功举办!

    2014-12-6~7日,共创力企业管理咨询为苏州某高科技企业提供了为期两天的<软件测试管理及调优实战>培训.此次培训由共创力研发咨询资深讲师杨学明先生主讲,杨老师在课前对客户的培训需求进行了充分的收集和了解,并与部分学员代表进行了沟通和交流,充分把握了课程中的的培训需求.两天的课程大家充分学习了软件测试管理.设计和软件性能测试调优及软件安全测试管理的内容,课程结束后,大家对课程给予了较高评价,收获较大,可以马上应用到工作中去,該公司将继续与杨老师合作,引进其他管理课程.

  • 连闯9关“杀”入微软new!(2005年12月版《智慧文摘》 霖志之)

    2000年6月,即将毕业的我在学校公告栏上看到微软亚洲技术中心将于本月某日在复旦大学举行校园招聘会的消息后,我即作了应聘的准备. 因为经常参加各种高水平的竞赛和考试,并且屡屡取得佳绩,所以自信心十足,丝毫不觉得自己比重点大学学生逊色.当天下午,当我赶到复旦大学第一教学楼时,召开宣讲会的大教室里已是人山人海,我刚够挤进教室门口.下午2点,宣讲会正式开始.先由微软人事经理作介绍,接着是2名微软员工代表现身说法,最后是当时担任亚洲技术中心总经理的唐骏作英语演讲.宣讲会开始后,还有很多人在不断地挤进来,

  • 4月27日微软云训练营活动-现场图集

    1.签到 2.到场同学,这一天是工作日,但是人气依然很火.

  • 12月16日参加了传说中的微软新产品发布会!----广州

    吃了一个极度难吃的饭盒! 不过下午的课程倒是不错的说!

  • 2004年12月26日闲逛微软新闻组摘录

    2004年12月26日18:22:29 Windows CE is not plug-play OS. The BIOS has to configure all PCI device correctly in order to make those PCI device work with Windows CE. 要帮助我们调整日常行为以赢得人心,请应用以下的G.R.E.A.T.步骤: 感激(Gratitude ) 永远要对人们给予你的快乐时光和好工作表示感激.从你的心底里说"谢谢"

Tags: