1572宝岛地图（预处理前缀和）

1572 宝岛地图

 

勇敢的水手们到达了一个小岛&＃xff0c;在这个小岛上&＃xff0c;曾经有海盗在这里埋下了一些宝藏。然而&＃xff0c;我们的船快抛锚了&＃xff0c;

与此同时&＃xff0c;船长发现藏宝图的一角被老鼠咬掉了一块。

藏宝图可以用一个n×m大小的矩形表示。矩形中的每一小块表示小岛中的一小块陆地&＃xff08;方块的边长为1米&＃xff09;。

有一些方块表示的是海&＃xff0c;这些块人是不能通过的。除了海不能走&＃xff0c;其它的小方块都是可以行走的。在可行走区

域里有一些小方块表示一些已知的地点。

另外&＃xff0c;在地图上有k条指令。每条指令的格式表示如下&＃xff1a;

“向y方向走n米”。

这里的方向有四种&＃xff1a;“北”&＃xff0c;“南”&＃xff0c;“东”&＃xff0c;“西”。如果你正确的跟着这些指令行走&＃xff0c;并且完整的执行完所有指令&＃xff0c;

你就可以找到宝藏所在的地点。

但是&＃xff0c;很不幸&＃xff0c;由于地图中好多地方都缺失了&＃xff0c;船长也不知道从哪些地方开始走。但是船长依然清楚地记得一

些已知的地点。另外&＃xff0c;船长也知道所有可行走区域。

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

思路&＃xff1a;

        这题乍一看即使预处理也要至少N*M&＃43;N*M*K的时间复杂度&＃xff0c;但题目明确说了大

写字母不会超过26个&＃xff0c;所以时间复杂度时N*M&＃43;26*K。完全可以暴力判断每个相应点

对于K条指令是否满足。

代码实现&＃xff1a;

#include
#include
#include
#include
#include
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int N&＃61;1000&＃43;100;
const int M&＃61;2e5&＃43;100;
char mp[N][N];
int bei[N][N],dong[N][N],xi[N][N];
int na[N][N];struct Node{int x,y;
}arr[N];struct query{char ch;int step;
}Q[M];char res[N];
int cnt,tot;
bool judge(int x,int y,int k){for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){char tmpc&＃61;Q[i].ch;int tmpx&＃61;Q[i].step;if(tmpc&＃61;&＃61;&＃39;N&＃39;){if(tmpx>&＃61;bei[x][y])return 0;x-&＃61;tmpx;}else if(tmpc&＃61;&＃61;&＃39;S&＃39;){if(tmpx>&＃61;na[x][y])return 0;x&＃43;&＃61;tmpx;}else if(tmpc&＃61;&＃61;&＃39;E&＃39;){if(tmpx>&＃61;dong[x][y])return 0;y&＃43;&＃61;tmpx;}else{if(tmpx>&＃61;xi[x][y])return 0;y-&＃61;tmpx;}}return 1;
}
int main(){int n,m,k;while(cin>>n>>m){memset(bei,0,sizeof(bei));memset(dong,0,sizeof(dong));memset(xi,0,sizeof(xi));memset(na,0,sizeof(na));memset(mp,&＃39;0&＃39;,sizeof(mp));tot&＃61;cnt&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%s",mp[i]&＃43;1);}cin>>k;for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){cin>>Q[i].ch>>Q[i].step;}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){if(mp[i][j]>&＃61;&＃39;A&＃39;&&mp[i][j]<&＃61;&＃39;Z&＃39;){arr[&＃43;&＃43;tot].x&＃61;i;arr[tot].y&＃61;j;}xi[i][j]&＃61;xi[i][j-1];if(mp[i][j]&＃61;&＃61;&＃39;#&＃39;)xi[i][j]&＃61;0;else xi[i][j]&＃43;&＃61;1;}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;m;j>&＃61;1;j--){dong[i][j]&＃61;dong[i][j&＃43;1];if(mp[i][j]&＃61;&＃61;&＃39;#&＃39;)dong[i][j]&＃61;0;else dong[i][j]&＃43;&＃61;1;}}for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){bei[j][i]&＃61;bei[j-1][i];if(mp[j][i]&＃61;&＃61;&＃39;#&＃39;)bei[j][i]&＃61;0;else bei[j][i]&＃43;&＃61;1;}}for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){for(int j&＃61;n;j>&＃61;1;j--){na[j][i]&＃61;na[j&＃43;1][i];if(mp[j][i]&＃61;&＃61;&＃39;#&＃39;)na[j][i]&＃61;0;else na[j][i]&＃43;&＃61;1;}}for(int i&＃61;1;i<&＃61;tot;i&＃43;&＃43;){if(judge(arr[i].x,arr[i].y,k)){res[&＃43;&＃43;cnt]&＃61;mp[arr[i].x][arr[i].y];}}sort(res&＃43;1,res&＃43;1&＃43;cnt);for(int i&＃61;1;i<&＃61;cnt;i&＃43;&＃43;){cout<}

THE END&＃xff1b;