目錄
大致題意：
思路：
代碼：
大致題意：
在一個圖中，一個人從(0,0)進行上下左右行走，有一個地雷點(mx,my)，詢問可不可以通過改變行走上下左右的順序(不改變上下左右走的次數)，可以避開雷，如果有多個，輸出任意一種，如果沒有，輸出Impossible!
思路：
看似復雜，其實細細想來，只有一個點是地雷，避免不了有：雷在起點和終點，不論怎么改變都至少有一個點會走重合且那個點是雷區，
還有一點，就是說無論怎么變換，最終都可以走到終點，
不妨讓向上下左右的在一塊，也就是向左走就一直向左走到盡頭，
如果UDLR都有，那么對于UDLR順序和LRDU順序會造成盡可能的不重復：
綠色：先上下后左右
棕色：先左右后上下
……
只要是對UDLR全排列，實質上就已經盡可能的避免了重復板塊，如果這樣都有重疊的，也就意味著再怎么打亂都會踩雷，
時間復雜度：
24(全排列)*1e5(走一遍)*2.4e6-綽綽有余，
代碼：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int mx,my;
int a[4] = {0,1,2,3};//U D L R
int cnt[4] = {0};
int op[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
bool check(){//模擬走
int x = 0,y = 0;
for(int i = 0;i < 4;i++){
for(int j = 0;j < cnt[a[i]];j++){
x+=op[a[i]][0];
y+=op[a[i]][1];
if(x == mx&&y == my) return false;
}
}
return true;
}
int main(){
int t;
cin >> t;
map<int,string>mp;
mp[0] = 'U'; mp[1] = 'D';
mp[2] = 'L'; mp[3] = 'R';
while(t--){
cin >> mx >> my;
string s;
cin >> s;
int x = 0,y = 0;
memset(cnt,0,sizeof(cnt));
a[0] = 0,a[1] = 1,a[2] = 2,a[3] = 3;
for(int i = 0;i < s.size();i++){//判斷終點位置 記錄每個方向能走的次數
if(s[i] == 'U'){
cnt[0]++; y++;
}
if(s[i] == 'D'){
cnt[1]++; y--;
}
if(s[i] == 'L'){
cnt[2]++; x--;
}
if(s[i] == 'R'){
cnt[3]++; x++;
}
}
if((mx == 0&&my == 0)||(x == mx&&y == my)){//不可能到達情況
cout << "Impossible\n";
continue;
}
bool ok = false;
do{
if(check()){
ok = true;//記錄已找到合適的路徑
for(int i = 0;i < 4;i++){
for(int j = 0;j< cnt[a[i]];j++)
cout<<mp[a[i]];
}
cout<<endl;
break;
}
}while(next_permutation(a,a+4));
if(!ok){
cout << "Impossible\n";
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239589.html
標籤：其他
上一篇：java實作貪吃蛇游戲