 /**//*
求S到T的字典序最小最短路径,其中路径最多只能包含k个不同的字符
n,m<=50 k<=4

我SB了,直接搜肯定不行的!
其实,由于木有什么障碍物,S到T的最短路其实就是哈密顿~~~
看wxyz的做法的
有k个字符的限制,k很小,要从这里入手
枚举可用的k个字符,然后bfs最短路

至于求字典序最小最短路时,我之前是按照zoj 3482求字典序最小反过来做 -------OMG
但这里就不能仅仅这样子了
如
cccT
aaca
Sdab
从往前S经过aa后,有两个c,不能确定选哪个了
可以先从T bfs到S,然后从S往回走,每次选择字母最小的走,如果有多个字母最小的,都加入
类似bfs那样扩展,一层一层
(不能从S扩展到T,然后从S推过去T,这里有可能字母最小的到不了T;或者从T推回去S,不一定字典序最小)


看别人的做法,有一种是用PQ搜的,好快!!
定义 operator < 为 -----------------------OMG
比较从S到该点距离+该点都T曼哈顿距离
比较S到该点的路径,取字典序小的
判重的状态时(mask, x, y) mask表示S到(x,y)这条路径上用的字母 -----------------------OMG
注意(x,y)压缩成x*100+y即可了,不要再开一个pair,会TLE

搜索思想主要是:贪心取总体最短的,再取字典序小的
判重不能够仅仅为(x,y),因为到达(x,y)的字典序很小的一条路径,有可能不会到达T~~~~~~~~~~~~
所以到达(x,y)需要加多一维,记录用过的字母mask
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const int INF = 0x3f3f3f3f;

char field[55][55];
int n, m, k;
int can;
int sx, sy, tx, ty;
 int dx[] = {0, 0, 1, -1};
 int dy[] = {1, -1, 0, 0};
string ans;
vector<char> vt;

bool out(int x, int y)
  {
return x < 0 || x >= n || y < 0 || y >= m;
}

void cal()
  {
int dist[55][55];
fill(dist[0], dist[n], INF);
queue<pair<int,int> > Q;
Q.push(make_pair(tx, ty));
dist[tx][ty] = 0;
 while(!Q.empty()) {
pair<int,int> now = Q.front(), next;
Q.pop();
 if (now == make_pair(sx, sy)) {
break;
}
 for (int i = 0; i < 4; i++) {
next = now;
next.first += dx[i];
next.second += dy[i];
if (out(next.first, next.second)
 || dist[next.first][next.second] != INF) {
continue;
}
 if (next != make_pair(sx, sy) && (can & (1<<field[next.first][next.second]-'a')) == 0) {
continue;
}
dist[next.first][next.second] = dist[now.first][now.second] + 1;
Q.push(next);
}
}

 if (dist[sx][sy] == INF) {
return;
}

int len = dist[sx][sy] - 1;
 if (ans != "-1" && len > ans.length()) {
return;
}

string path;
vector<pair<int,int> > vt[2];
int p = 0, q = 1;
vt[p].push_back(make_pair(sx, sy));
 for (int i = 0; i < len ; i++) {//一层一层扩展,每次选字母最小的(允许多个)
vt[q].clear();
 for (vector<pair<int,int> >::iterator it = vt[p].begin(); it != vt[p].end(); it++) {
pair<int,int> now = *it, next;
 for (int i = 0; i < 4; i++) {
next = now;
next.first += dx[i];
next.second += dy[i];
if (out(next.first, next.second)
 || dist[next.first][next.second] != dist[now.first][now.second] - 1) {
continue;
}
 if (vt[q].empty()) {
vt[q].push_back(next);
 } else {
pair<int,int> &f = vt[q].front();
 if (field[f.first][f.second] > field[next.first][next.second]) {
vt[q].clear();
vt[q].push_back(next);
 } else if (field[f.first][f.second] == field[next.first][next.second]) {
vt[q].push_back(next);
}
}
}
}
sort(vt[q].begin(), vt[q].end());
vt[q].resize(unique(vt[q].begin(), vt[q].end()) - vt[q].begin());
pair<int,int> &f = vt[q].front();
path += field[f.first][f.second];
swap(p, q);
}

 if (ans == "-1" || len < ans.length()) {
ans = path;
return ;
}
 if (ans > path) {
ans = path;
}
}

void dfs(int pos, int have)
  {
 if (have == k) {
cal();
return ;
}
 for (int i = pos; i < vt.size(); i++) {
can ^= (1<<vt[i]);
dfs(i+1, have+1);
can ^= (1<<vt[i]);
}
}


int dist(const pair<int,int> &a, const pair<int,int> &b)
  {
return abs(a.first-b.first) + abs(a.second-b.second);
}

struct Node
  {
string path;
pair<int,int> pos;
int mask;

 Node() {}
Node(string _path, pair<int,int> _pos, int _mask)
 {
path = _path;
pos = _pos;
mask = _mask;
}
};

pair<int,int> T;


bool operator < (const Node &A, const Node &B)
  {
 if (A.path.length() + dist(A.pos, T) != B.path.length() + dist(B.pos, T)) {
return A.path.length() + dist(A.pos, T) > B.path.length() + dist(B.pos, T);
}
return A.path > B.path;
}

inline int lowbit(int mask)
  {
return mask & (-mask);
}

inline int bitcount(int mask)
  {
int cnt = 0;
 while(mask > 0) {
cnt ++;
mask -= lowbit(mask);
}
return cnt;
}

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

 for (; ~scanf("%d%d%d", &n, &m, &k); ) {
vt.clear();
 for (int i = 0; i < n ; i++) {
scanf("%s", field[i]);
 for (int j = 0;j < m; j++) {
 if (field[i][j] == 'S') {
sx = i;
sy = j;
 } else if(field[i][j] == 'T') {
tx = i;
ty = j;
 } else {
vt.push_back(field[i][j] - 'a');
}
}
}
 /**//*
sort(vt.begin(), vt.end());
vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
k = min(k, (int)vt.size());
ans = "-1";
can = 0;
dfs(0, 0);
*/
string ans = "-1";
//少一个pair速度快好多!!!!
//直接用*即可!!!
set<pair<int,int> > iset;//加维
T = make_pair(tx, ty);
priority_queue<Node> PQ;
PQ.push(Node("", make_pair(sx,sy), 0));
 while(!PQ.empty()) {
Node now = PQ.top();
PQ.pop();
 if (now.pos == T) {
ans = now.path;
break;
}
 if (iset.count(make_pair(now.mask, now.pos.first*100+now.pos.second)) > 0) {
continue;
}
iset.insert(make_pair(now.mask, now.pos.first*100+now.pos.second));
 for (int i = 0; i < 4; i++) {
pair<int,int> npos = now.pos;
npos.first += dx[i];
npos.second += dy[i];
 if (out(npos.first, npos.second)) {
continue;
}
int mask = now.mask;
string path = now.path;
 if (field[npos.first][npos.second] != 'T') {
mask |= 1<<(field[npos.first][npos.second]-'a');
path += field[npos.first][npos.second];
}
 if (iset.count(make_pair(mask, npos.first*100+npos.second)) > 0) {
continue;
}
 if (bitcount(mask) <= k) {
PQ.push(Node(path, npos, mask));
}
}
}
cout<<ans<<endl;
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|