题意:
给出一个字符串,炸弹的坐标;
从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;
}