题目:

这题如果没有时间限制的话暴力可以解,暴力的话时间复杂度大概是O(k*n),1s的话非常悬。

所以我们需要换个思路,我们对每个点预处理四个方向最多能走的步数,这个预处理时间复杂度是O(n*m)。

然后对每个字母点模拟一下即可。总时间复杂度O(n*m+k)。不会超时。

提示:没有满足要求的点时,要输出"no solution",我就在这个上面WA了一次,不然应该可以一次AC的。

代码:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <queue>
using namespace std;
typedef long long ll;
#define INF 2147483647 // 上N,下S,右E,左W。 //输入
int n,m,k;
char a[][];
struct node1{
int dir;int len;
}t[]; //b[i][j][k]表示点(i,j)往方向k最多可以走的步数。
int b[][][]; //字母点
struct node{
int x;int y;char g;
bool operator<(node b)
{
return g < b.g;
}
};
list <node> l;
list <node>::iterator it; int d[][] = {-,,,,,,,-}; //模拟q这个点走的过程
bool can(node q) {
int x = q.x;int y = q.y;
for(int i = ;i < k; i++){
node1 s = t[i];
if(b[x][y][s.dir] < s.len) return false;
x = x + d[s.dir][]*s.len;
y = y + d[s.dir][]*s.len;
}
return true;
} int main(){
//输入数据
cin >> n >> m;
node e;
for(int i = ;i <= n; i++) {
for(int j = ;j <= m; j++) {
cin >> a[i][j];
if(a[i][j] != '#' && a[i][j] != '.'){
e.x = i; e.y = j; e.g = a[i][j];
l.push_back(e);
}
}
}
//对子母点按字典序排序
l.sort(); for(int j = ;j <= m; j++){
//预处理每个点最多能往北边走多少步
int num = ;
for(int i = ;i <= n; i++){
if(a[i][j] != '#'){
b[i][j][] = num;num++;
}else{
num = ;
}
}
//预处理每个点最多能往南边走多少步
num = ;
for(int i = n; i >= ; i--){
if(a[i][j] != '#'){
b[i][j][] = num; num++;
}else{
num = ;
}
}
} for(int i = ; i <= n; i++){
//预处理每个点最多能往东边走多少步
int num = ;
for(int j = ;j <= m; j++){
if(a[i][j] != '#'){
b[i][j][] = num; num++;
}else{
num = ;
}
}
//预处理每个点最多能往西边走多少步
num = ;
for(int j = m; j >= ; j--){
if(a[i][j] != '#'){
b[i][j][] = num; num++;
}else{
num = ;
}
}
} //把字母方向转换成数字表示
cin >> k;
char key;
for(int i = ;i < k; i++){
cin >> key >> t[i].len;
if(key == 'N') t[i].dir = ;
else if(key == 'S') t[i].dir = ;
else if(key == 'E') t[i].dir = ;
else if(key == 'W') t[i].dir = ;
} //对每个子母点进行模拟
bool flag = false;
for(it = l.begin();it != l.end(); it++){
node q = *it;
if(can(q)){
cout << q.g;
flag = true;
}
}
if(!flag) cout << "no solution";
cout << endl;
return ;
}

最新文章

  1. 12个学习 CSS3 网站布局设计的优秀案例
  2. Error -27780: [GENERAL_MSG_CAT_SSL_ERROR]connect to host &quot;124.202.213.70&quot; failed: [10054] Connection reset by peer [MsgId: MERR-27780]
  3. IIS配置ASP.NET和服务器错误页
  4. memcached学习笔记1--概念
  5. Lombok - 消除冗长的 java 代码
  6. 安装 Visual Stuidio 2010 失败
  7. OA学习笔记-004-Spring2.5配置
  8. [Angular 2] 9. Replace ng-modle with #ref &amp; events
  9. ViewPager禁止滑动以及它与内层滑动控件水平方向上事件冲突的解决方法
  10. python 文件中的中文编码解决方法
  11. c++一些面试题目
  12. Linux(CentOS)安装配置zeromq、jzmq(解决各种问题)
  13. eclipse使用技巧---使用正则表达式查找替换
  14. XSS DOM 测试
  15. nlp L1
  16. Perl包和模块(内容来自beginning perl)
  17. FTC诉高通垄断案苹果从中受益
  18. leetcode283
  19. 超级wifi
  20. 振动器(Vibrator)

热门文章

  1. Solidworks.2016.SP5下载安装破解图文教程
  2. javascript中document.getElementsByClassName兼容性封装方法一
  3. R dataframe 去除行号
  4. mysql中间件研究(tddl atlas cobar sharding-jdbc)
  5. ZBrush 4R7中自定义笔刷
  6. Qwiklab&#39;实验-API Gateway, AWS Lambda&#39;
  7. npx命令
  8. UVALive-8072 Keeping On Track 树形dp 联通块之间缺失边的个数
  9. HDU-2955 Robberies 浮点数01背包 自变量和因变量位置互换
  10. PHP下的异步尝试一:初识生成器