周三要考试，可是根本就踏实不下来复习，毕设也静不下心弄了。于是就玩玩比赛了，晚上12点还有一场CF，到时候再玩个1个多小时去睡觉。
说说我周赛做的两道题吧：
Open the Lock
一个四位数变成另一个四位数，要求的操作有三种：
1. 对任意一位加1，如果大于9，回到1
2. 对任意一位减1，如果小于1，回到9
3. 交换相邻两位的数字，最左边和最右边不算相邻
可以知道状态空间为9*9*9*9<10^4，直接BFS搞就可以了，因为我大量使用STL，导致TLE了，后来改成int，就AC了，代码如下：
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <set> using namespace std; const int MAX = 2005; //string a, b; int a, b; int hash[100 * 100]; int ten[4] = {1, 10, 100, 1000}; int GetHash(int x) { return x; } int Add(int x, int i) { int t = (x / ten[i]) % 10; if(t < 9) return x + ten[i]; else return x - t * ten[i] + ten[i]; } int Sub(int x, int i) { int t = (x / ten[i]) % 10; if(t > 1) return x - ten[i]; else return x - t * ten[i] + 9 * ten[i]; } int Swp(int x, int i) { int t1 = (x / ten[i]) % 10; int t2 = (x / ten[i + 1]) % 10; return x - t1 * ten[i] - t2 * ten[i + 1] + t2 * ten[i] + t1 * ten[i + 1]; } int go() { vector<int> ans; vector<int> Q; //set<string> one; Q.push_back(a); ans.push_back(0); //one.insert(a); memset(hash, 0, sizeof(hash)); hash[GetHash(a)] = 1; for(int i = 0; i < Q.size(); i++) { //printf("$%d\n", Q[i]); if(Q[i] == b) { //printf("%d %d\n", Q[i], b); return ans[i]; } for(int j = 0; j < 4; j++) { int strAdd = Add(Q[i], j); int strSub = Sub(Q[i], j); //if(one.find(strAdd) == one.end()) if(hash[GetHash(strAdd)] == 0) { //one.insert(strAdd); Q.push_back(strAdd); ans.push_back(ans[i] + 1); hash[GetHash(strAdd)] = 1; } //else return ans[i] + 1; //if(one.find(strSub) == one.end()) if(hash[GetHash(strSub)] == 0) { //one.insert(strSub); Q.push_back(strSub); ans.push_back(ans[i] + 1); hash[GetHash(strSub)] = 1; } //else return ans[i] + 1; if(j < 3) { int strSwp = Swp(Q[i], j); //if(one.find(strSwp) == one.end()) if(hash[GetHash(strSwp)] == 0) { //one.insert(strSwp); Q.push_back(strSwp); ans.push_back(ans[i] + 1); hash[GetHash(strSwp)] = 1; } // else return ans[i] + 1; } } } } int main() { int T; scanf("%d", &T); while(T--) { //cin >> a >> b; scanf("%d%d", &a, &b); printf("%d\n", go()); } }
诡异的楼梯
一张20*20的地图，上满有障碍点，非障碍点，楼梯三种格子，起点、终点落在非障碍点上，梯子每分钟改变一个朝向（横着，竖着），从起点到终点，四个方向，问说最少的步数，走楼梯的话，就一下子跨两格。
设置一个这样的状态(x,y,step)，花费的空间也就20*20*400左右，然后去BFS，这样是可以AC的，有趣的是，我觉得只要存step的奇偶性就行了，也就是这样的状态(x,y,step%2)，我觉得这样是对的，但一时不知道怎么严谨说明，大概就是，如果先扩展到一个奇数步的节点的话，那么这个就是奇数所能到达的最小的走法了，看着代码虽然100+行，但是自己看了看，发现其实也没啥东西，代码如下：
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <set> using namespace std; const int MAX = 25; int m, n, sx, sy, ex, ey; char mm[MAX][MAX]; int hash[405 * 410]; class CNODE { public: int x, y, t; public: CNODE() {} CNODE(int _x, int _y, int _t) : x(_x), y(_y), t(_t) {} int GetHash() { int res = 0; res += (x * 20 + y); res = res * 410 + (t % 2); //res = res * 410 + t; return res; } }; int go() { memset(hash, 0, sizeof(hash)); vector<CNODE> Q; Q.push_back(CNODE(sx, sy, 0)); hash[Q[0].GetHash()] = 1; for(int i = 0; i < Q.size(); i++) { int x = Q[i].x; int y = Q[i].y; int t = Q[i].t; if(x == ex && y == ey) return t; CNODE dd = CNODE(x, y, t + 1); if(hash[dd.GetHash()] == 0) { hash[dd.GetHash()] = 1; Q.push_back(dd); } for(int j = -1; j <= 1; j++) for(int k = -1; k <= 1; k++) if(j * j + k * k == 1) { int dx = x + j; int dy = y + k; if(dx < 0 || dx >= m || dy < 0 || dy >= n) continue; if(mm[dx][dy] == '*') continue; CNODE dq; if(mm[dx][dy] == '.' || mm[dx][dy] == 'T' || mm[dx][dy] == 'S') { dq = CNODE(dx, dy, t + 1); if(hash[dq.GetHash()] == 0) { hash[dq.GetHash()] = 1; Q.push_back(dq); } if(dx == ex && dy == ey) return t + 1; } else { if((mm[dx][dy] == '|' && k == 0 && t % 2 == 0) || (mm[dx][dy] == '-' && k == 0 && t % 2 == 1)) { if(dx + j >= 0 && dx + j < m) { dq = CNODE(dx + j, dy, t + 1); if(hash[dq.GetHash()] == 0) { hash[dq.GetHash()] = 1; Q.push_back(dq); } if(dx == ex && dy == ey) return t + 1; } } if((mm[dx][dy] == '-' && j == 0 && t % 2 == 0) || (mm[dx][dy] == '|' && j == 0 && t % 2 == 1)) { if(dy + k >= 0 && dy + k < n) { dq = CNODE(dx, dy + k, t + 1); if(hash[dq.GetHash()] == 0) { hash[dq.GetHash()] = 1; Q.push_back(dq); } if(dx == ex && dy == ey) return t + 1; } } } } } printf("no\n"); } int main() { while(scanf("%d%d", &m, &n) != EOF) { for(int i = 0; i < m; i++) { scanf("%s", mm[i]); for(int j = 0; j < n; j++) { if(mm[i][j] == 'S') sx = i, sy = j; if(mm[i][j] == 'T') ex = i, ey = j; } } printf("%d\n", go()); } }转载于:https://www.cnblogs.com/litstrong/archive/2011/03/20/1989792.html
