/**//* 求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
搜索
最新评论
|
|