2021 9.15 p.m.小结

T2：问题 B: 龙&虫

题目描述

    给出一张NxM的地图,在地图上有一只虫,样子却很像龙，而目嘴能快速地喷(直射)出一种毒液,瞬间杀死敌人。
    现在假设虫的初始位置在(X1,Y1),另外在(X2,Y2)处有一个敌人。假设虫移动一步需要单位1的时间,而杀死敌人不需要时间,并且虫的毒液射程无穷大,但毒液不能穿透阻碍物，虫只能攻击上、下、左、右、左上、右上、左下、右下八个方向。
    请求出虫最少需要用多少时间才能消灭敌人。

输入

    第1行为2个数N和M,表示矩阵的规模(N为高,M为宽)。
    接下来是NxM的矩阵,O表示空地,X表示障碍物。
    下面是若千行数据，每行为一对数据,分别是敌人的位置和虫的位置。显然,敌人和虫都不可能在障碍物上。
    以“0000”为输人结束标志。

输出

    输出第1行为虫能消灭掉敌人的最短时间。
    显然,若能直接打到敌人,则时间为0;若无法消灭,则第2行再输出"Impossible!"。

样例输入

3 4

OXXO

XXOO

XOOO

3 2 2 4

3 3 1 1

0 0 0 0

样例输出

1

Impossible!

提示

【数据规模】

对于30%的数据满足:NxM<5000。

对于50%的数据满足:NxM<10000。

对于100%的数据满足:NxM<20000。

题解

这道题不难 ^%^#@@$%%^，只是压缩得比较恶心。如果说压缩了，也过样例了，却TLE了，那么有一个东西可能没整对：千万不要预处理出能够直接连通的两个点！这样会TLE。逆向思维，只要把敌人的八个方向的位置标出来就可以了，不要虫每移一下就看能不能扫到敌人，这样效率过不去。搞定了这点，剩下的最令人恶心的就是压缩了。其实完全可以写一个模板，对于压缩问题，每次用同样的方式压缩图、点阵，为了节约空间，一种最基本的压缩就是对于点（x，y），存在map[(x-1)*m+y]里，这样是绝对能保证唯一性的，因为相当于把图平摊成了一条线……格外注意，先输入敌人的坐标，再输入虫的坐标。（因为这一点我连续WA了N次）。

参考代码

#include
#include
#include
#include

T3：问题 C: 有重复元素的排列问题

题目描述

设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法，列出R的所有不同排列。
给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。

输入

第1 行是元素个数n，1≤n≤500。接下来的1 行是待排列的n个元素。

输出

计算出的n个元素的所有不同排列。最后1行中的数是排列总数。

样例输入

4

aacc

样例输出

aacc

acac

acca

caac

caca

ccaa

6

题解

听说stl里面专门有针对这个问题的函数，此处就不深究了。比起普通的求解全排列，这道题n的范围明显大得多。可是由于重复元素的出现，结果可能不是很大。但是如果还按照全排列那样搜，就会TLE。现在来看看有什么不同？当枚举到第k个位置时，只关注还能取哪些字母，因此完全可以用一个数组存每种字母还可以用多少次，然后用一个get数组从当前类型的字母直接跳到下一类型的字母（或者直接开另一新数组存所有字母“类型”）。如此就可以在可接受效率内完成本题。

参考代码

#include
#include
using namespace std;
int n,x[10000],tot=0;char s[10000];
int a[10000],get22[10000],col=0,cnt=0,sis[10000];
void dfs(int k)
{if(k==n+1){tot++;for(int i=1;i<=n;i++)printf("%c",x[i]);printf("\n");return;} for(int i=1;i;i=get22[i]){if(!sis[a[i]]) continue;sis[a[i]]--;x[k]=a[i];dfs(k+1);sis[a[i]]++;}
}
int main()
{scanf("%d",&n);scanf("%s",s);for(int i=1;i<=n;i++)a[i]=s[i-1];sort(a+1,a+n+1);for(int i=n;i>=1;i--){sis[a[i]]++;get22[i]=col;if(a[i]!=a[i-1]) col=i;}dfs(1);printf("%d",tot);return 0;
}

T4:问题 D: 警察找车

题目描述

    年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车,但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。
    那个装置太旧了,以至于只能发射关于那辆车的移动路线的方向信息。
    编写程序,通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。
    小镇的地图是矩形的,上面的符号用来标明哪儿可以行车和哪儿不行。“.” 表示小镇上那块地方是可以行车的,而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。
    汽车能向四个方向移动:向北(向上)、向南(向下)、向西(向左)、向东(向右)。
    拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向,拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

输入

    第1行包含两个自然数R和C,之间用1个空格隔开,1≤N≤50,1≤C≤50,分别表示小镇地图中的行数和列数。
    以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位,符号之间没有空格。
    接下来的第R+2行包含1个自然数N,1≤N≤1000,表示一组方向的长度（方向数据个数）。
    接下来的N行,每行包含单词NORTH(北)、SOUTH(南)、WEST(西)和EAST(东)中的任一个、它们表示汽车移动的方向,任何两个连续的方向都不相同。

输出

用R行表示的小镇的地图(像输人文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。

样例输入

4 5

.....

.X...

...*X

X.X..

3

NORTH

WEST

SOUTH

样例输出

.....

*X*..

*.*.X

X.X..

题解

如果说，第一眼看到这题认为是搜索，那么恭喜，TLE。这题可以搜索做，但是明显是没必要的，每一步都写好了该怎么走，还需要搜索吗？直接模拟就行了呗。每走一步，都可以从上一步*位置走，然后先把能走到的位置标位#，在扫描完之后统一改成下一个过程的*，至于可能会有重复？别担心，这样更节约效率，因为当前你走的这个点能够把被覆盖的点所需要走的过程全部走了，可以视作完全覆盖。用这种模拟的思想，就能够在规定时间内完成这道题。

参考代码

#include
using namespace std;
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int n,m,e_map[200][200];char s[200];
int st_x,st_y,a[1200],q,vis[200][200];
bool pd(int x,int y)
{ return (x>0)&&(x<=n)&&(y>0)&&(y<=m); }
void dfs(int k)
{if(k==q+1) return;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(e_map[i][j]==2){e_map[i][j]=0;int i1=i+dx[a[k]],j1=j+dy[a[k]];while(pd(i1,j1)&&e_map[i1][j1]!=1){e_map[i1][j1]=3;//相当于改成#i1+=dx[a[k]];j1+=dy[a[k]];}}}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(e_map[i][j]==3)e_map[i][j]=2;dfs(k+1);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s);for(int j=1;j<=m;j++){if(s[j-1]=='*') e_map[i][j]=2;else if(s[j-1]=='X')e_map[i][j]=1;}}scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%s",s);if(s[0]=='E') a[i]=1;else if(s[0]=='S') a[i]=2;else if(s[0]=='W') a[i]=3;else a[i]=4;}dfs(1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(e_map[i][j]==1) printf("X");else if(e_map[i][j]==2) printf("*");else printf(".");}printf("\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！