51nod 1572 宝岛地图

1572 宝岛地图

题目来源: CodeForces

基准时间限制:1 秒 空间限制:131072 KB

勇敢的水手们到达了一个小岛,在这个小岛上,曾经有海盗在这里埋下了一些宝藏。然而,我们的船快抛锚了,与此同时,船长发现藏宝图的一角被老鼠咬掉了一块。

藏宝图可以用一个n×m大小的矩形表示。矩形中的每一小块表示小岛中的一小块陆地(方块的边长为1米)。有一些方块表示的是海,这些块人是不能通过的。除了海不能走,其它的小方块都是可以行走的。在可行走区域里有一些小方块表示一些已知的地点。

另外,在地图上有k条指令。每条指令的格式表示如下:

“向y方向走n米”。

这里的方向有四种:“北”,“南”,“东”,“西”。如果你正确的跟着这些指令行走,并且完整的执行完所有指令,你就可以找到宝藏所在的地点。

但是,很不幸,由于地图中好多地方都缺失了,船长也不知道从哪些地方开始走。但是船长依然清楚地记得一些已知的地点。另外,船长也知道所有可行走区域。

现在船长想知道从哪些已知地点出发,按照指令,可能找到宝藏所在地。

Input

单组测试数据
第一行包含两整数n和m(3≤n,m≤1000)。
接下来的n行每行有m个字符,表示整个地图。
“#”代表海。在地图矩形中,矩形的四周一圈一定是海。
“.”代表可行走区域,未知地点。大写字母“A”到“Z”表示可行走区域,已知地点。
所有大写字母不一定都被用到。每个字母在地图中最多出现一次。所有已知地点用不同的大写字母表示。

接下来一行有一个整数k(1≤k≤10^5),接下来有k行。
每行表示一条指令。
指令格式为“dir len”,“dir”表示朝哪个方向走,“len”表示走几步。
“dir”有四种取值“N”,“S”,“E”,“W”,对应题目中的“北”,“南”,“东”,“西”
在地图中,北是在顶部,南是在底部,西是在左边,东是在右边。“len”是一个整数,范围在[1,1000]。

Output

共一行,按字典序升序打印出所有可以完整执行地图中指令的已知区域的字母,如果没有满足要求的已知区域,则打印“no solution”(没有引号)。

Input示例

输入样例1
6 10
##########
#K#..#####
#.#..##.##
#..L.#...#
###D###A.#
##########
4
N 2
S 1
E 1
W 2

Output示例

输出样例1
AD

先用dp预处理一下每个点向四个方向能走的最远距离dp[i][j][0]代表从(i,j)向上最多走多少步,dp[i][j][1]代表从(i,j)向左最多走多少步,dp[i][j][2]代表从(i,j)向下最多走多少步,dp[i][j][3]代表从(i,j)向右最多走多少步然后就直接模拟就行了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1<<28;
const int maxn=1010;
const int maxm=110;
const int maxk=100010;
const int mod=1e9+7;
const double pi=acos(-1.0);
int n,m;
char mapp[maxn][maxn];
int dp[maxn][maxn][4];
void init()
{

    //0代表向上,1代表向左
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(mapp[i][j]==‘#‘)
                dp[i][j][0]=dp[i][j][1]=-1;
            else
            {
                dp[i][j][0]=dp[i-1][j][0]+1;
                dp[i][j][1]=dp[i][j-1][1]+1;
            }
        }
    //2代表向下,3代表向右
    for(int i=n-1;i>=0;i--)
        for(int j=m-1;j>=0;j--)
        {
            if(mapp[i][j]==‘#‘)
                dp[i][j][2]=dp[i][j][3]=-1;
            else
            {
                dp[i][j][2]=dp[i+1][j][2]+1;
                dp[i][j][3]=dp[i][j+1][3]+1;
            }
        }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        int x[30],y[30];
        cls(x,-1);cls(y,-1);
        for(int i=0;i<n;i++)
        {
            scanf("%s",mapp[i]);
            for(int j=0;j<m;j++)
            if(mapp[i][j]>=‘A‘&&mapp[i][j]<=‘Z‘)
            {
                x[mapp[i][j]-‘A‘]=i;
                y[mapp[i][j]-‘A‘]=j;
            }
        }
        init();
        int k;
        scanf("%d",&k);
        int dir[maxk],len[maxk];
        for(int i=0;i<k;i++)
        {
            char op[2];
            scanf("%s%d",op,&len[i]);
            if(op[0]==‘N‘) dir[i]=0;
            else if(op[0]==‘W‘) dir[i]=1;
            else if(op[0]==‘S‘) dir[i]=2;
            else if(op[0]==‘E‘) dir[i]=3;
        }
        int noso=1;
        for(int i=0;i<26;i++)
        {
            if(x[i]!=-1&&y[i]!=-1)
            {
                int posx=x[i],posy=y[i];
                int flag=1;
                for(int j=0;j<k;j++)
                {
                    if(len[j]>dp[posx][posy][dir[j]])
                        {flag=0;break;}
                    else
                    {
                        if(dir[j]==0) posx-=len[j];
                        else if(dir[j]==1) posy-=len[j];
                        else if(dir[j]==2) posx+=len[j];
                        else if(dir[j]==3) posy+=len[j];
                    }
                }
                if(flag) {noso=0;printf("%c",i+‘A‘);}
            }
        }
        if(noso) printf("no solution");
        printf("\n");
    }
    return 0;
}
 
时间: 05-18

51nod 1572 宝岛地图的相关文章

第四章 搜索(深度、广度搜索、全排列、走迷宫、再解炸弹人、宝岛探险、水管工游戏)

一.深度优先搜索DFS 深度优先搜索DFS的关键思想是:当下应该怎么做(每个方法都试一遍),这一步解决后,进入下一步,下一步的解决方法和这一步的解决方法是一样的 DFS的基本模型 void dfs(int step) { 判断边界 尝试每一种可能  for(i=1;i<=n;i++) { 继续下一步 dfs(step+1) } 返回 } 1.1全排列 1 //输入一个数n 2 //输出1-n的全排列 3 #include <stdio.h> 4 int n, book[10], a[10

51nod 1191 消灭兔子

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1191 有N只兔子,每只有一个血量B[i],需要用箭杀死免子.有M种不同类型的箭可以选择,每种箭对兔子的伤害值分别为D[i],价格为P[i](1 <= i <= M).假设每种箭只能使用一次,每只免子也只能被射一次,计算要消灭地图上的所有兔子最少需要多少Q币.如不能杀死所有兔子,请输出No Solution. 特别说明:1.当箭的伤害值大于等于兔子的血量时,能将兔子杀死

百度地图API实现批量地址解析

1.前言 写这篇文章的原因是最近做一个GIS项目在网上爬取了一些数据,无奈只有地址的文字信息没有坐标信息,如何把信息显现在地图上呢?很纠结啊,查看了一下百度地图API惊奇的发现百度提供了地址解析的API,然后查看了他的Demo后豁然开朗,所以动手将自己的文字信息数据进行解析坐标信息.下面开始讲解. 2.方案 (1)自己数据库中的数据 (2)百度地图API Demo <!DOCTYPE html> <html> <head> <meta http-equiv=&qu

【API】高德地图API JS实现获取坐标和回显点标记

1.搜索+选择+获取经纬度和详细地址 2.回显数据并点标记 3.实现 第一步:引入资源文件 <!--引入高德地图JSAPI --><script src="//webapi.amap.com/maps?v=1.3&key=在官网申请一个key"></script><!--引入UI组件库(1.0版本) --><script src="//webapi.amap.com/ui/1.0/main.js">

js中实现高德地图坐标经纬度转百度地图坐标

1 function tobdMap(x, y) { 2 var x_pi = 3.14159265358979324 * 3000.0 / 180.0; 3 var z = Math.sqrt(x * x + y * y) + 0.00002 * Math.sin(y * x_pi); 4 var theta = Math.atan2(y, x) + 0.000003 * Math.cos(x * x_pi); 5 var bd_lon = z * Math.cos(theta) + 0.00

DEDE5.7如何制作网站地图?

DEDE用的人很多,可能大家在使用的过程中会碰到一些问 题,这很正常的,今天我们来讲讲DEDE5.7如何制作网站地图,其实网站地图分两种,一种做给网友看的,方便网友可以方便地找到自己想浏览的内容,另外 一种是做给搜索引擎蜘蛛看,方便蜘蛛在你网站上面抓取内容.    当然,我们这里讲的主要是针对蜘蛛的,因为DEDE默认的就有针对用户的网站地图,主要是以栏目的形式展现,这个可以在DEDE后台自行生成.其实大家印象当中的网站地图是XML格式的,一般命名成sitemap.xml,接下来进入正题.    

baidu地图:实现多点连线渲染

<script type="text/javascript"> var points = [ {"Lng":120.17787645967861,"Lat":30.251826748722667}, {"Lng":120.17786646842835,"Lat":30.251826580357911} ]; </script> <!DOCTYPE html> <ht

51nod 1201 整数划分(dp)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201 题解:显然是一道dp,不妨设dp[i][j]表示数字i分成j个一共有几种分法. 那么转移方程式为: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] 表示将i - 1划分为j个数,然后j个数都+1 还是不重复,将i - 1划分为j - 1个数,然后j - 1个数都+1,再加上1这个数. 然后就是j的范围要知道1+2+

Vue2.0与 [百度地图] 结合使用———vue+webpack+axios+百度地图实现组件之间的通信

Vue2.0与 [百度地图] 结合使用: 1.vue init webpack-simple vue-baidu-map 2.下载axios cnpm install axios; 3.在main.js中引入axios,并使用 import axios from 'axios' /* 把axios对象挂到Vue实例上面,其他组件在使用axios的时候直接 this.$http就可以了 */ Vue.prototype.$http = axios; 4.引入百度地图的js秘钥--->最好在inde