第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)Evil Coordinate (全排列)
2021/5/12 12:26:38
本文主要是介绍第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)Evil Coordinate (全排列),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题意:
给出一个字符串,炸弹的坐标;
从0,0点出发,按照字符串所给出的方向走,如果中途踩到炸弹,则需要重新排列字符串使路径中没有炸弹,输出排列后的路径字符串,否则输出“Impossible”,
思路1:
这个是当时的思路,但是因为码力比较弱,没写对;
-
炸弹的坐标在0,0或者说在终点的位置,直接输出"Impossible";
-
终点在坐标轴上,炸弹也在坐标轴上;例如在x轴上
如果上下走的步数为0,则输出"Impossible",否则我们就可以先上再左右再下;
另一种情况炸弹在终点右侧,则先左后右y轴同理分析
-
终点不在坐标轴上
如果炸弹在1,就走2号线,如果在2就走1号线,如果都不在,两条线都可以走; -
走的每一次都要走到尽头,即向左走就走到尽头
Code:
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <utility> #include <stack> #include <map> #include <vector> #include <set> #include <iomanip> #define hz020 return #define mes memset #define mec memcpy using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int>pii; const int N = 1000010; const int null = 0x3f3f3f3f; const ll mod = 1000000007; int T; int x,y; int main() { scanf("%d",&T); while(T --) { cin >> x >> y; string s; cin >> s; int u = 0,d = 0,l = 0,r = 0,idx = 0,idy = 0; for(int i = 0;i < s.size();i ++) { if(s[i] == 'U') u ++,idy ++; else if(s[i] == 'D') d ++,idy --; else if(s[i] == 'R') r ++,idx ++; else if(s[i] == 'L') l ++,idx --; // cout << idx << " " << idy << endl; } // cout << idx << endl << idy << endl; if((x == idx && y == idy) || (x == 0 && y == 0)) puts("Impossible"); else if(idx == x && idy != y)//终点和炸弹都在一条竖线上 { if(idx == 0 && l == 0 && r == 0)//y轴上并且不可以左右走 { if(idy >= y && y >= 0 && idy >= 0) puts("Impossible");//y正半轴,炸弹在终点下方 else if(idy <= y && y <= 0 && idy <= 0) puts("Impossible");//y负半轴,炸弹在终点上方 else if(y < 0)//炸弹在负半轴 { for(int i = 1;i <= u;i ++) cout << "U"; for(int i = 1;i <= d;i ++) cout << "D"; puts(""); } else if(y > 0)//炸弹在正半轴 { for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= u;i ++) cout << "U"; puts(""); } } else if(idx == 0)//终点和炸弹都在y轴上,但是左右步数不为0 { for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= u;i ++) cout << "U"; for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= r;i ++) cout << "R"; puts(""); } else//终点和炸弹在一条竖线上且不在坐标轴上 { for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= u;i ++) cout << "U"; for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; puts(""); } } else if(idy == y && idx != x) //终点和炸弹在一条直线上 { if(idy == 0 && u == 0 && d == 0)//终点和炸弹在x轴上,且不可以上下移动 { if(idx >= x && x >= 0 && idx >= 0) puts("Impossible");//x正半轴,炸弹在终点左侧 else if(idx <= x && idx <= 0 && x <= 0) puts("Impossible");//x负半轴,炸弹在终点右侧 else if(x > 0)//炸弹在正半轴 { for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; puts(""); } else if(x < 0) //炸弹在负半轴 { for(int i = 1;i <= r;i ++) cout << "R"; for(int i = 1;i <= l;i ++) cout << "L"; puts(""); } } else if(idy == 0) //炸弹和终点都在x轴但是可以上下走 { for(int i = 1;i <= u;i ++) cout << "U"; for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; for(int i = 1;i <= d;i ++) cout << "D"; puts(""); } else//终点和炸弹在一条横线上且不在坐标轴上 { for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= u;i ++) cout << "U"; puts(""); } } else { if(y == 0) // 在剩下的横轴 { for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= u;i ++) cout << "U"; for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; puts(""); } else // 在剩下的竖轴 { for(int i = 1;i <= l;i ++) cout << "L"; for(int i = 1;i <= r;i ++) cout << "R"; for(int i = 1;i <= d;i ++) cout << "D"; for(int i = 1;i <= u;i ++) cout << "U"; puts(""); } } } hz020 0; }
思路2:
因为炸弹只有一个点,我们将上下左右规划到一个点,将四个方向进行全排列,在每一次排列中判断路径上是否有地雷;
Code:
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <utility> #include <stack> #include <map> #include <vector> #include <set> #include <iomanip> #define hz020 return #define mes memset #define mec memcpy using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int>pii; const int N = 1000010; const int null = 0x3f3f3f3f; const ll mod = 1000000007; int T; int x,y; int cnt[210];//记录次数 int d[2][4] = {{0,1,0,-1},{1,0,-1,0}}; string str = "URDL"; int main() { scanf("%d",&T); while(T --) { mes(cnt,0,sizeof cnt); cin >> x >> y; string s; cin >> s; for(auto i:s) cnt[i] ++; int idy = cnt[str[0]] - cnt[str[2]],idx = cnt[str[1]] - cnt[str[3]]; if((x == idx && y == idy) || (x == 0 && y == 0)) { puts("Impossible"); continue; } int p[4] = {0,1,2,3};//代表方向 do { idx = 0,idy = 0; string ss; for(int i = 0;i < 4;i ++) { for(int j = 0;j < cnt[str[p[i]]];j ++) { ss += str[p[i]]; idx += d[0][p[i]]; idy += d[1][p[i]]; if(idx == x && idy == y) goto pjq; } } cout << ss << endl; goto pjq0200; pjq:; }while(next_permutation(p,p + 4)); cout << "Impossible" << endl; pjq0200:; } hz020 0; }
这篇关于第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)Evil Coordinate (全排列)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享