51nod 1572 宝岛地图 (预处理四个方向的最大步数优化时间,时间复杂度O(n*m+k))
2024-09-02 01:08:55
题目:
这题如果没有时间限制的话暴力可以解,暴力的话时间复杂度大概是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 ;
}
最新文章
- 12个学习 CSS3 网站布局设计的优秀案例
- Error -27780: [GENERAL_MSG_CAT_SSL_ERROR]connect to host ";124.202.213.70"; failed: [10054] Connection reset by peer [MsgId: MERR-27780]
- IIS配置ASP.NET和服务器错误页
- memcached学习笔记1--概念
- Lombok - 消除冗长的 java 代码
- 安装 Visual Stuidio 2010 失败
- OA学习笔记-004-Spring2.5配置
- [Angular 2] 9. Replace ng-modle with #ref &; events
- ViewPager禁止滑动以及它与内层滑动控件水平方向上事件冲突的解决方法
- python 文件中的中文编码解决方法
- c++一些面试题目
- Linux(CentOS)安装配置zeromq、jzmq(解决各种问题)
- eclipse使用技巧---使用正则表达式查找替换
- XSS DOM 测试
- nlp L1
- Perl包和模块(内容来自beginning perl)
- FTC诉高通垄断案苹果从中受益
- leetcode283
- 超级wifi
- 振动器(Vibrator)
热门文章
- Solidworks.2016.SP5下载安装破解图文教程
- javascript中document.getElementsByClassName兼容性封装方法一
- R dataframe 去除行号
- mysql中间件研究(tddl atlas cobar sharding-jdbc)
- ZBrush 4R7中自定义笔刷
- Qwiklab&#39;实验-API Gateway, AWS Lambda&#39;
- npx命令
- UVALive-8072 Keeping On Track 树形dp 联通块之间缺失边的个数
- HDU-2955 Robberies 浮点数01背包 自变量和因变量位置互换
- PHP下的异步尝试一:初识生成器