给一个n*m的图， 图上有n个标号， n<=4， 然后有墙， 还有一个终点x。 每一步， 只能走某一个标号， 可以向四个方向走， 然后必须要碰到墙或者图的边界或者另一个标号才能停下来。 问你在t步之内能否使第一个标号到达终点。
因为有一个上限t。 所以直接bfs就可以， 感觉思路不是很难， 但是写代码+调试花了超级久...不过总算1A， 不然就懵逼了。
#include <bits/stdc++.h> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<11 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 7777777; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; struct node { vector<pll> a; int step; node() { step = 0; } }; int cnt, w, h; map <vector<pll>, int> mp; vector <int> row[11], col[11]; pll target; char s[11][11]; int bfs(const node& init, int t) { queue <node> q; q.push(init); while(!q.empty()) { node tmp = q.front(); q.pop(); if(tmp.step > t) continue; if(tmp.a[0] == target) { return tmp.step; } for(int i = 0; i < cnt; i++) { int x = tmp.a[i].fi, y = tmp.a[i].se; int tmpy = *(--lower_bound(row[x].begin(), row[x].end(), y)); for(int j = 0; j < cnt; j++) { if(i == j) continue; if(tmp.a[i].fi == tmp.a[j].fi && tmp.a[i].se > tmp.a[j].se) { tmpy = max(tmpy, tmp.a[j].se); } } tmpy++; vector<pll> ha(tmp.a); ha[i].se = tmpy; if(!mp[ha]) { node newNode = tmp; newNode.a[i].se = tmpy; newNode.step++; q.push(newNode); mp[ha] = 1; } x = tmp.a[i].fi, y = tmp.a[i].se; tmpy = *lower_bound(row[x].begin(), row[x].end(), y); for(int j = 0; j < cnt; j++) { if(i == j) continue; if(tmp.a[i].fi == tmp.a[j].fi && tmp.a[i].se < tmp.a[j].se) { tmpy = min(tmpy, tmp.a[j].se); } } tmpy--; ha = tmp.a; ha[i].se = tmpy; if(!mp[ha]) { node newNode = tmp; newNode.a[i].se = tmpy; newNode.step++; mp[ha] = 1; q.push(newNode); } x = tmp.a[i].fi, y = tmp.a[i].se; int tmpx = *(--lower_bound(col[y].begin(), col[y].end(), x)); for(int j = 0; j < cnt; j++) { if(i == j) continue; if(tmp.a[i].se == tmp.a[j].se && tmp.a[i].fi > tmp.a[j].fi) { tmpx = max(tmpx, tmp.a[j].fi); } } tmpx++; ha = tmp.a; ha[i].fi = tmpx; if(!mp[ha]) { node newNode = tmp; newNode.a[i].fi = tmpx; newNode.step++; q.push(newNode); mp[ha] = 1; } x = tmp.a[i].fi, y = tmp.a[i].se; tmpx = *lower_bound(col[y].begin(), col[y].end(), x); for(int j = 0; j < cnt; j++) { if(i == j) continue; if(tmp.a[i].se == tmp.a[j].se && tmp.a[i].fi < tmp.a[j].fi) { tmpx = min(tmpx, tmp.a[j].fi); } } tmpx--; ha = tmp.a; ha[i].fi = tmpx; if(!mp[ha]) { node newNode = tmp; newNode.a[i].fi = tmpx; newNode.step++; q.push(newNode); mp[ha] = 1; } } } return -1; } int main() { int t; while(cin>>cnt>>w>>h>>t) { mp.clear(); for(int i = 0; i < h; i++) { scanf("%s", s[i]); } for(int i = 0; i < h; i++) { row[i].clear(); row[i].pb(-1); row[i].pb(w); } for(int i = 0; i < w; i++) { col[i].clear(); col[i].pb(-1); col[i].pb(h); } node init; for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { if(s[i][j] == 'X') target = mk(i, j); if(s[i][j] == 'W') { row[i].pb(j); col[j].pb(i); } } } for(int i = 1; i <= cnt; i++) { for(int j = 0; j < h; j++) { for(int k = 0; k < w; k++) { if(s[j][k]-'0' == i) { init.a.pb(mk(j, k)); } } } } for(int i = 0; i < h; i++) { sort(row[i].begin(), row[i].end()); } for(int i = 0; i < w; i++) sort(col[i].begin(), col[i].end()); mp[init.a] = 1; int ans = bfs(init, t); if(ans == -1) { puts("NO SOLUTION"); } else { cout<<ans<<endl; } } }