題目：

這題如果沒有時間限制的話暴力可以解，暴力的話時間復雜度大概是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[1010][1010]; struct node1{int dir;int len; }t[100010];//b[i][j][k]表示點(i，j)往方向k最多可以走的步數。 int b[1010][1010][4]; //字母點 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[4][2] = {-1,0,1,0,0,1,0,-1};//模擬q這個點走的過程 bool can(node q) {int x = q.x;int y = q.y;for(int i = 0;i < k; i++){ node1 s = t[i];if(b[x][y][s.dir] < s.len) return false;x = x + d[s.dir][0]*s.len;y = y + d[s.dir][1]*s.len;}return true; }int main(){//輸入數據 cin >> n >> m;node e;for(int i = 1;i <= n; i++) {for(int j = 1;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 = 1;j <= m; j++){//預處理每個點最多能往北邊走多少步 int num = 0;for(int i = 1;i <= n; i++){if(a[i][j] != '#'){b[i][j][0] = num;num++;}else{num = 0;}}//預處理每個點最多能往南邊走多少步num = 0;for(int i = n; i >= 1; i--){if(a[i][j] != '#'){b[i][j][1] = num; num++;}else{num = 0;}}}for(int i = 1; i <= n; i++){//預處理每個點最多能往東邊走多少步int num = 0;for(int j = 1;j <= m; j++){if(a[i][j] != '#'){b[i][j][3] = num; num++;}else{num = 0;}}//預處理每個點最多能往西邊走多少步num = 0;for(int j = m; j >= 1; j--){if(a[i][j] != '#'){b[i][j][2] = num; num++;}else{num = 0;}}}//把字母方向轉換成數字表示 cin >> k;char key;for(int i = 0;i < k; i++){cin >> key >> t[i].len;if(key == 'N') t[i].dir = 0;else if(key == 'S') t[i].dir = 1;else if(key == 'E') t[i].dir = 2;else if(key == 'W') t[i].dir = 3;}//對每個子母點進行模擬 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 0; }

總結

以上是生活随笔為你收集整理的51nod 1572 宝岛地图 （预处理四个方向的最大步数优化时间，时间复杂度O（n*m+k））的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。