终于肝完了。。
专题二的题大都挺好的，但有些题意不太清楚，特此说明一下。。(几个月没写博客突然感觉不会写了。。)
A - Eight
虽然是八数码问题，但常规的康托展开加bfs却会超时，这个时候就需要用更加高深的算法了，网上也有许多对八数码问题的解法，这里提一个比较特别的做法:打表。
已知最终的状态就是12345678X，那么我们可以用最终状态逆推所有可以到达他的状态，并且记录路径就行了。
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 10;
int fa[maxn];
int ans[maxn];
bool ok[maxn];
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
char d[5] = "udlr";
int fact[10];
int state[maxn][9];
void init1()
{fact[0] = 1;for (int i = 1;i < 9;i++)fact[i] = fact[i - 1] * i;
}
int kt(int s[], int n)
{int ans = 0, cnt = 0;for (int i = 0;i < n;i++){cnt = 0;for (int j = i + 1;j < n;j++)if (s[j] < s[i])cnt++;ans += cnt*fact[n - i - 1];}return ans;
}
int theid;
void init2()
{int temp[9];for (int i = 0;i < 9;i++)temp[i] = (i + 1) % 9;theid = kt(temp, 9);memcpy(state[theid], temp, sizeof(temp));queue<int>Q;Q.push(theid);ok[theid] = 1;while (!Q.empty()){int u = Q.front();Q.pop();int p = 0;while (state[u][p] != 0)p++;int tx = p / 3, ty = p % 3;memcpy(temp, state[u], sizeof(state[u]));for (int i = 0;i < 4;i++){int x = tx + dir[i][0];int y = ty + dir[i][1];if (x >= 0 && x < 3 && y >= 0 && y < 3){swap(temp[tx * 3 + ty], temp[x * 3 + y]);int id = kt(temp, 9);if (!ok[id]){memcpy(state[id], temp, sizeof(temp));ok[id] = 1;Q.push(id);fa[id] = u;ans[id] = i;}swap(temp[tx * 3 + ty], temp[x * 3 + y]);}}}
}
int map[9];
bool read()
{string s;if (getline(cin, s)){int now = 0;int Size = s.size();for (int i = 0;i < Size;i++)if (s[i] != ' ')map[now++] = (s[i] == 'x' ? 0 : s[i] - '0');return 1;}return 0;
}
void out(int idx)
{while (idx!=theid){printf("%c", d[(ans[idx] ^ 1)]);idx = fa[idx];}printf("\n");}
int main()
{init1();init2();while (read()){int id = kt(map, 9);if (!ok[id]){puts("unsolvable");continue;}out(id);}}一次打表，终身受益啊。。
B - Eight II
B题同理，也可以用打表来做，先看代码。
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;int fact[10];
void init2()
{fact[0] = 1;for (int i = 1;i < 9;i++)fact[i] = fact[i - 1] * i;
}int kt(int s[], int n)
{int ans = 0;int cnt = 0;for (int i = 0;i < n;i++){cnt = 0;for (int j = i + 1;j < n;j++)if (s[i] > s[j])cnt++;ans += cnt*fact[n - i - 1];}return ans;
}struct node
{int x, y;int map[10];int knum;node(string s){//memcpy(map, s, sizeof(map));for (int i = 0;i < 9;i++){if (s[i] == 'X'){map[i] = 0;x = i / 3;y = i % 3;}elsemap[i] = s[i] - '0';}knum = kt(map, 9);}node(int s[], int _x, int _y, int _ktnum){memcpy(map, s, sizeof(map));x = _x;y = _y;knum = _ktnum;}};
const int maxn = 1e6 + 5;
int fa[10][maxn];
int ans[10][maxn];
queue<node>Q;
bool vis[maxn];
int dir[4][2] = { 1,0,0,-1,0,1,-1,0 };char d[5] = "dlru";vector<char>V;void BFS(node a,int num)
{//while (!Q.empty())Q.pop();memset(vis, 0, sizeof(vis));vis[a.knum] = 1;Q.push(a);while (!Q.empty()){node u = Q.front();Q.pop();int thex = u.x, they = u.y;for (int i = 0;i < 4;i++){int tempx = u.x + dir[i][0];int tempy = u.y + dir[i][1];if (tempx < 0 || tempx>2 || tempy < 0 || tempy>2)continue;int temp[10];memcpy(temp, u.map, sizeof(u.map));swap(temp[tempx * 3 + tempy], temp[u.x*3+u.y]);int tmpkt = kt(temp, 9);if (vis[tmpkt])continue;fa[num][tmpkt] = u.knum;vis[tmpkt] = 1;ans[num][tmpkt] = i;node v = node(temp, tempx, tempy, tmpkt);Q.push(v);}}
}void init()
{memset(fa, -1, sizeof(fa));init2();node a = node("X12345678");BFS(a,0);a = node("1X2345678");BFS(a,1);a = node("12X345678");BFS(a,2);a = node("123X45678");BFS(a,3);a = node("1234X5678");BFS(a,4);a = node("12345X678");BFS(a, 5);a = node("123456X78");BFS(a, 6);a = node("1234567X8");BFS(a, 7);a = node("12345678X");BFS(a, 8);
}
int num[10];
int bb[10];
int main()
{init();//freopen("D:\\input.txt", "r", stdin);//freopen("D:\\1.txt", "w", stdout);int T;scanf("%d", &T);int cas = 1;while (T--){string a, b;cin >> a >> b;memset(num, 0, sizeof(num));memset(bb, 0, sizeof(bb));int pos;for (int i = 0, j=0;i < 9;i++){if (a[i] == 'X')pos = i;elsenum[a[i] - '0'] = j++;}for (int i = 0;i < 9;i++){if (b[i] == 'X')continue;b[i] = num[b[i] - '0'] + '1';bb[i] = b[i] - '0';}V.clear();int bkt = kt(bb, 9);while (fa[pos][bkt]!=-1){V.push_back(d[ans[pos][bkt]]);bkt = fa[pos][bkt];}printf("Case %d: %d\n", cas++, V.size());for(int i=V.size()-1;i>=0;i--)printf("%c", V[i]);printf("\n");}return 0;}首先打出X在所有位置的表，但同上一题不同的是，最终态并不是我们表中的状态，而是自己输入的。这个应该怎么转换呢？
（这里要仔细思考思考。。）
我们需要将初始状态变成形如表中的状态，我们知道表中的状态所有能到达的状态，所以，就可以知道表中的状态到最终状态的路径。所以关键就是如何将初始状态变成表中的状态。
我们可以发现，不管状态怎么变，它的下标仍然是从0到8，那么我们只要知道初始状态中的值与它的下标对应关系，就可以将它变成表中的状态了，注意既然初始状态变了，那么最终态也应该用同样的对应关系改变。
因为下标是0到8，我们需要的是1到9，其中又有一个X，其实转换有点麻烦，但代码中的转换有点巧妙，大家可以自己思考思考。
C - 哈密顿绕行世界问题
简单的dfs即可。。(数据特别水。。)
D - Escape
bfs加预处理即可。一开始以为要计算所有大炮对一个点的作用，但之后看题解才恍然大悟，因为炮台会阻挡大炮，所以只有处理所有方向的第一个炮台的作用就行了。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;bool cat[105][105];
bool hurt[105][105][1002];struct castle
{char s[3];int t, v, x, y;castle(char _s[], int _t, int _v, int _x, int _y){s[0] = _s[0];t = _t, v = _v, x = _x, y = _y;}castle(){}
}Cat[105];
int m, n, k, d;
void init() {int x, y, v, t;for (int i = 0;i < k;i++) {x = Cat[i].x, y = Cat[i].y, v = Cat[i].v, t = Cat[i].t;if (Cat[i].s[0] == 'E') {int stop = n;for (int j = x + 1; j <= n; j++) {if (cat[j][y]) {stop = j;break;}}int curTime = 1;for (int j = x + v;j <= stop;j += v, curTime++) {for (int k = curTime;k <= d;k += t) {hurt[j][y][k] = true;}}}else if (Cat[i].s[0] == 'W') {int stop = 0;for (int j = x - 1; j >= 0; j--) {if (cat[j][y]) {stop = j;break;}}int curTime = 1;for (int j = x - v;j >= stop;j -= v, curTime++) {for (int k = curTime;k <= d;k += t) {hurt[j][y][k] = true;}}}else if (Cat[i].s[0] == 'N') {int stop = 0;for (int j = y - 1; j >= 0; j--) {if (cat[x][j]) {stop = j;break;}}int curTime = 1;for (int j = y - v;j >= stop;j -= v, curTime++) {for (int k = curTime;k <= d;k += t) {hurt[x][j][k] = true;}}}else if (Cat[i].s[0] == 'S') {int stop = m;for (int j = y + 1; j <= m; j++) {if (cat[x][j]) {stop = j;break;}}int curTime = 1;for (int j = y + v;j <= stop;j += v, curTime++) {for (int k = curTime;k <= d;k += t) {hurt[x][j][k] = true;}}}}
}
struct node
{int x, y, step;node(int _x,int _y,int _step):x(_x),y(_y),step(_step){}
};
int dir[5][2] = { -1,0,1,0,0,-1,0,1,0,0 };bool vis[105][105][1002];void solve()
{node start = node(0, 0, 0);vis[0][0][0] = 1;queue<node>Q;Q.push(start);int ans = 0;while (!Q.empty()){node u = Q.front();Q.pop();if (u.x == n&&u.y == m){ans = u.step;break;}for (int i = 0;i < 5;i++){int tempx = u.x + dir[i][0];int tempy = u.y + dir[i][1];if (tempx<0 || tempx>n || tempy<0 || tempy>m)continue;if (hurt[tempx][tempy][u.step + 1])continue;if (vis[tempx][tempy][u.step + 1])continue;if (u.step + 1 > d)break;if (cat[tempx][tempy])continue;node v = node(tempx, tempy, u.step + 1);vis[tempx][tempy][u.step + 1] = 1;Q.push(v);}}if (ans)printf("%d\n", ans);else puts("Bad luck!");
}int main()
{while (~scanf("%d %d %d %d",&m,&n,&k,&d)){memset(cat, 0, sizeof(cat));memset(hurt, 0, sizeof(hurt));memset(vis, 0, sizeof(vis));char s[3];int t, v, x, y;for (int i = 0;i < k;i++){scanf("%s %d %d %d %d", s, &t, &v, &y, &x);cat[x][y] = 1;Cat[i] = castle(s, t, v, x, y);}if (cat[n][m]){puts("Bad luck!");continue;}init();solve();}
}ida*限制深度即可。
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string Seq[10];
int n;
struct node
{int pos[10];node() { memset(pos, 0, sizeof(pos)); }
}temp;
char DNA[5] = "ACTG";
bool dfs(node u, int dep, int limit)
{if (dep > limit)return 0;for (int i = 0;i < n;i++)if (limit - dep < Seq[i].size() - u.pos[i])return 0;bool flag = true;for (int i = 0;i < n;i++)if (Seq[i].size() != u.pos[i]) { flag = false;break; }if (flag)return 1;for (int i = 0;i < 4;i++){node v = u;flag = false;for (int j = 0;j < n;j++){if (u.pos[j] < Seq[j].size() && DNA[i] == Seq[j][u.pos[j]]){flag = true;v.pos[j] = u.pos[j] + 1;}elsev.pos[j] = u.pos[j];}if (flag&&dfs(v, dep + 1, limit))return 1;}return false;
}int main()
{int T;scanf("%d", &T);while (T--){scanf("%d", &n);for (int i = 0;i < n;i++)cin >> Seq[i];int i;for ( i = 0;;i++)if (dfs(temp, 0, i))break;cout << i << endl;}}题目太水的，爆搜即可。
这题让我学到了这一类的题该怎么做，一共操作数6*2个，我们可以用数组来记录这些值怎么变，i和i^1是一对，从i变成i^1就代表旋转，至于顺时针还是逆时针则可以看i的奇偶。
#include<iostream>
#include<cstring>
using namespace std;
int Rotate[15][20] = {{ 1,4,7,13,25,37,46,49,52,21,33,45,10,11,12,24,36,35,34,22 },{ 45,33,21,1,4,7,13,25,37,52,49,46,34,22,10,11,12,24,36,35 },{ 7,8,9,16,28,40,48,47,46,36,24,12,13,14,15,27,39,38,37,25 },{ 36,24,12,7,8,9,16,28,40,48,47,46,37,25,13,14,15,27,39,38 },{ 9,6,3,19,31,43,54,51,48,39,27,15,16,17,18,30,42,41,40,28 },{ 39,27,15,9,6,3,19,31,43,54,51,48,40,28,16,17,18,30,42,41 },{ 42,30,18,3,2,1,10,22,34,52,53,54,19,20,21,33,45,44,43,31 },{ 52,53,54,42,30,18,3,2,1,10,22,34,43,31,19,20,21,33,45,44 },{ 15,14,13,12,11,10,21,20,19,18,17,16,1,2,3,6,9,8,7,4 },{ 18,17,16,15,14,13,12,11,10,21,20,19,7,4,1,2,3,6,9,8 },{ 37,38,39,40,41,42,43,44,45,34,35,36,46,47,48,51,54,53,52,49 },{ 34,35,36,37,38,39,40,41,42,43,44,45,52,49,46,47,48,51,54,53 }
};
char map[100];
int center[6] = { 5,29,50,23,26,32 };
int thface[6][10] =
{{ 1,2,3,4,6,7,8,9 },{ 16,17,18,30,42,41,40,28 },{ 46,47,48,51,54,53,52,49 },{ 10,11,12,24,36,35,34,22 },{ 13,14,15,27,39,38,37,25 },{ 19,20,21,33,45,44,43,31 },
};int get_h()
{int ans = 0;for (int i = 0;i < 6;i++){int cnt = 0;for (int j = 0;j < 8;j++)if (map[center[i]] != map[thface[i][j]])cnt++;ans += cnt;}return ans;
}int face[10], way[10];bool dfs(int dep, int limit)
{if (limit < dep)return 0;int h = get_h();//if (limit - dep < h / 12)return 0;if (h == 0)return 1;char tempmap[100];for (int i = 0;i < 12;i++){face[dep] = i / 2;way[dep] = i % 2 ? -1 : 1;memcpy(tempmap, map, sizeof(map));for (int j = 0;j < 20;j++)map[Rotate[i][j]] = tempmap[Rotate[i ^ 1][j]];if (dfs(dep + 1, limit))return true;memcpy(map, tempmap, sizeof(tempmap));}return false;
}
void scan(char &c) {char cc;while (cc = getchar(), cc<'a' || cc>'z');c = cc;
}
int main()
{int T;scanf("%d", &T);while (T--){for (int i = 1;i <= 54;i++)scan(map[i]);if (get_h() == 0){printf("0\n");continue;}int d;for (d = 1;d <= 5;d++)if (dfs(0, d))break;if (d == 6)puts("-1");else{printf("%d\n", d);for (int i = 0;i < d;i++)printf("%d %d\n", face[i], way[i]);}}
}G - Nightmare Ⅱ
以为和简单搜索里面的fire一样两个移动单位放入队列里面，但仔细想想其实有很多不同。。
1，fire里面的火不能穿墙，但ghost可以穿墙，所以这里就可以用哈密顿距离来判断是否会遇到鬼而不用将鬼放入队列中了(长见识了。。)
2，little erriyue1s可以走3步。。
3,little erriyue和他的girl friend竟然可以呆在原地(坑。)
所以这题用双向队列比较好，因为第二点，我们需要枚举3次little erriyue走路。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char map[805][805];
int n, m;
struct node
{int x, y;node(int _x,int _y):x(_x),y(_y){}node(){}
};
queue<node>Q[2];
node ghost[2],G,M;
int step;
bool vis[805][805][2];
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };bool inmap(int x, int y)
{if (x >= 1 && x <= n&&y >= 1 && y <= m)return 1;return 0;
}bool hurt(int x, int y)
{if ((abs(ghost[0].x - x) + abs(ghost[0].y - y)) <= step * 2)return false;if ((abs(ghost[1].x - x) + abs(ghost[1].y - y)) <= step * 2)return false;return true;
}bool bfs(int c)
{int Size = Q[c].size();while (Size--){node u = Q[c].front();Q[c].pop();if (!hurt(u.x, u.y))continue;for (int i = 0;i < 4;i++){int tempx = u.x + dir[i][0];int tempy = u.y + dir[i][1];if (!inmap(tempx, tempy))continue;if (!hurt(tempx, tempy))continue;if (map[tempx][tempy] == 'X')continue;if (!vis[tempx][tempy][c]){if (vis[tempx][tempy][c ^ 1])return true;vis[tempx][tempy][c] = 1;Q[c].push(node(tempx, tempy));}}}return false;
}int solve()
{while (!Q[0].empty())Q[0].pop();while (!Q[1].empty())Q[1].pop();memset(vis, 0, sizeof(vis));step = 0;Q[0].push(M);Q[1].push(G);vis[M.x][M.y][0] = vis[G.x][G.y][1] = 1;while (!Q[0].empty()||!Q[1].empty()){step++;if (bfs(0))return step;if (bfs(0))return step;if (bfs(0))return step;if (bfs(1))return step;}return -1;}int main()
{int T;scanf("%d", &T);while (T--){scanf("%d %d", &n, &m);for (int i = 1;i <= n;i++)scanf("%s", map[i] + 1);int g = 0;for(int i=1;i<=n;i++)for (int j = 1;j <= m;j++){if (map[i][j] == 'M')M.x = i, M.y = j;if (map[i][j] == 'G')G.x = i, G.y = j;if (map[i][j] == 'Z')ghost[g].x = i, ghost[g++].y = j;}cout << solve() << endl;}return 0;}一开始不知道层数，以为用ida*可以解决，然而第二个样例就跑不出来，没想到简单的bfs就行了。。
bfs+map判重即可。
#include <stdio.h>
#include <string.h>
#include <string>
#include <queue>
#include <map> using namespace std;const char aimStr[] = {11, 12, 13, 14, 15, 16, 17, 1,21, 22, 23, 24, 25, 26, 27, 1,31, 32, 33, 34, 35, 36, 37, 1,41, 42, 43, 44, 45, 46, 47, 1, 0
};
struct Node {char str[36];int steps;
};
char buf[36];void Move(Node &now, int val) {for (int i = 0; ; ++i)if (now.str[i] == val) {now.str[i] = 1;return;}
}int BFS() {queue<Node> Q;Node tmp, now;strcpy(now.str, buf);now.steps = 0;Q.push(now);map<string, int> mp;int mpid = 1, i, j;mp[buf] = mpid++;if (mp[aimStr] == mp[buf]) return 0;mp[aimStr] = mpid++;while (!Q.empty()) {now = Q.front(); Q.pop();for (i = 0; i < 32; ++i) {if (now.str[i] == 1 && now.str[i - 1] != 1&& now.str[i - 1] % 10 != 7) {tmp = now;Move(tmp, tmp.str[i - 1] + 1);tmp.str[i] = tmp.str[i - 1] + 1;++tmp.steps;if (mp[tmp.str] == mp[aimStr]) return tmp.steps;if (mp[tmp.str] == 0) {mp[tmp.str] = mpid++;Q.push(tmp);}}}}return -1;
}int main() {// freopen("stdin.txt", "r", stdin); int n, i, j, k, tmp;scanf("%d", &n);while (n--) {for (i = k = 0; i < 4; ++i) {buf[k++] = (i + 1) * 10 + 1;for (j = 1; j < 8; ++j) {scanf("%d", &tmp);buf[k] = tmp;if (buf[k] % 10 == 1)buf[k] = 1;++k;}}printf("%d\n", BFS());}return 0;
}BFS即可
注意几个坑点。。
1，小于等于T时间都行
2，小心两边都是传送门
#include<iostream>
#include<queue>
#include<cstring>
#include<stdio.h>
using namespace std;char map[3][15][15];
int Px, Py, Pz;
struct node
{int x, y, z;int step;node(int _x, int _y, int _z,int _step){x = _x, y = _y, z = _z;step = _step;}
};
queue<node>Q;
bool vis[3][15][15];
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
int N, M, T;
void solve()
{memset(vis, 0, sizeof(vis));while (!Q.empty())Q.pop();node start = node(1, 1, 0, 0);Q.push(start);vis[0][1][1] = 1;bool flag = false;while (!Q.empty()){node u = Q.front();Q.pop();if (u.x == Px&&u.y == Py&&u.z == Pz&&u.step <= T){flag = true;break;}for (int i = 0;i < 4;i++){int tempx = u.x + dir[i][0];int tempy = u.y + dir[i][1];if (tempx<1 || tempx>N || tempy<1 || tempy>M)continue;if (map[u.z][tempx][tempy] == '*')continue;if (map[u.z][tempx][tempy] == '#'){if (map[u.z ^ 1][tempx][tempy] == '*'||map[u.z^1][tempx][tempy]=='#')continue;if (!vis[u.z ^ 1][tempx][tempy]){vis[u.z ^ 1][tempx][tempy] = 1;node temp = node(tempx, tempy, u.z ^ 1, u.step+1);Q.push(temp);}}else if (!vis[u.z][tempx][tempy]){vis[u.z][tempx][tempy] = 1;node temp = node(tempx, tempy, u.z, u.step + 1);Q.push(temp);}}}if (flag)puts("YES");elseputs("NO");
}
int main()
{int TT;scanf("%d", &TT);while (TT--){scanf("%d %d %d", &N, &M, &T);for (int i = 1;i <= N;i++)scanf("%s", map[0][i] + 1);for (int i = 1;i <= N;i++)scanf("%s", map[1][i] + 1);for(int i=0;i<2;i++)for(int j=1;j<=N;j++)for (int k = 1;k <= M;k++){if (map[i][j][k] == 'P'){Px = j;Py = k;Pz = i;}}solve();}
}
好题!
注意一个坑，就是he doesn't want to visit a city more than twice!，也就是每个城市最多可以经过2次，这也就是为什么用3进制来保存状态。
dp[i][state]代表目前在第i个城市，经过城市的状态为state。
状态转移也就是dp[j][state+fact[i]]=min(dp[j][state+fact[i]],dp[i][state]+cost[i][j])
具体代码如下：
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;int cost[15][15];
int fact[15];
const int inf = 0x3f3f3f;
void init()
{fact[1] = 3;for (int i = 2;i < 12;i++)fact[i] = fact[i - 1] * 3;
}struct node
{int state, now;
};
int dp[15][180000];
int n, m;void solve()
{queue<node>Q;memset(dp, inf, sizeof(dp));for (int i = 1;i <= n;i++){node temp;temp.state = fact[i];temp.now = i;Q.push(temp);dp[i][temp.state] = 0;}int mincost = inf;while (!Q.empty()){node u = Q.front();Q.pop();for (int i = 1;i <= n;i++){if (i == u.now)continue;if ((u.state%fact[i + 1] - u.state%fact[i]) / fact[i] == 2)continue;if (dp[i][u.state + fact[i]] > dp[u.now][u.state] + cost[u.now][i]){dp[i][u.state + fact[i]] = dp[u.now][u.state] + cost[u.now][i];node v;v.state = u.state + fact[i];v.now = i;//Q.push(v);bool flag = true;int tmp = v.state;tmp /= 3;for (int i = 1;i <= n;i++){if (tmp % 3 == 0){flag = false;break;}tmp /= 3;}if (flag)mincost = min(mincost, dp[i][u.state+fact[i]]);elseQ.push(v);}}}if (mincost == inf)puts("-1");elseprintf("%d\n", mincost);}int main()
{init();while (~scanf("%d %d",&n,&m)){int a, b, c;memset(cost, inf, sizeof(cost));for (int i = 1;i <= m;i++){scanf("%d %d %d", &a, &b, &c);cost[a][b]= min(cost[a][b],c);cost[b][a] = cost[a][b];}solve();}}继续加油吧~