首页 > 代码库 > HDU 5010 Get the Nut(2014 ACM/ICPC Asia Regional Xi'an Online)
HDU 5010 Get the Nut(2014 ACM/ICPC Asia Regional Xi'an Online)
思路：广搜， 因为空格加上动物最多只有32个那么对这32个进行编号，就能可以用一个数字来表示状态了，因为只有 ‘P’ ‘S‘ ‘M‘ ‘.‘ 那么就可以用4进制刚好可以用64位表示。
接下去每次就是模拟了。
注意： ‘S’ 不是只有一个。
一个东西如果不是‘P‘在动的话要先判断周围有没有‘P’，有的话要先吃掉
‘P‘在动的时候如果一个位置周围有多个东西，都要吃掉。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<map>#include<set>#include<time.h>#include<string>#define REP(i,n) for(int i=0;i<n;++i)#define REP1(i,a,b) for(int i=a;i<=b;++i)#define REP2(i,a,b) for(int i=a;i>=b;--i)#define MP make_pair#define LL long long#define ULL unsigned long long#define X first#define Y second#define MAXN 1000050using namespace std;map<ULL, int> mp;int dx[] = { 0, 0, 1, -1 };int dy[] = { 1, -1, 0, 0 };char s[6][9];int id[6][9];int qx[100];int qy[100];int qcnt;ULL q[MAXN];ULL bas[100];struct node { char a[6][9]; int scnt; node() { } ; node(ULL now) { scnt = 0; REP(i,6) REP(j,8) a[i][j] = s[i][j]; REP(i,qcnt) { ULL k = now & 3; now >>= 2; if (k == 0) continue; if (k == 1) { a[qx[i]][qy[i]] = ‘S‘; scnt++; } if (k == 2) a[qx[i]][qy[i]] = ‘M‘; if (k == 3) a[qx[i]][qy[i]] = ‘P‘; } } void debug(){ puts("-------"); REP(i,6) { REP(j,8)putchar(a[i][j]); puts(""); } puts("------------------"); }};void init() { qcnt = 0; int cid = 0; memset(id, -1, sizeof(id)); REP(i,6) REP(j,8) { if (s[i][j] == ‘#‘ || s[i][j] == ‘N‘) continue; qx[qcnt] = i; qy[qcnt++] = j; id[i][j] = cid++; }}ULL geths(char s[6][9]) { ULL ans = 0; REP(i,6) REP(j,8) { if (s[i][j] == ‘S‘) { ans += bas[id[i][j] << 1]; continue; } if (s[i][j] == ‘M‘) { ans += 2 * bas[id[i][j] << 1]; continue; } if (s[i][j] == ‘P‘) { ans += 3 * bas[id[i][j] << 1]; } } return ans;}bool check(int x, int y) { if (x < 0 || x >= 6 || y < 0 || y >= 8) return false; return true;}node move(node a, int x, int y, int dxx, int dyy, int &p) { char c = a.a[x][y]; while (true) { int xx = x + dxx; int yy = y + dyy; if ((!check(xx, yy)) || a.a[xx][yy] != ‘.‘) { p = 1; return a; } a.a[xx][yy] = a.a[x][y]; a.a[x][y] = ‘.‘; if (c == ‘P‘) { int flag=0; for (int j = 0; j < 4; ++j) { int px = xx + dx[j]; int py = yy + dy[j]; if (!check(px, py)) continue; if (a.a[px][py] == ‘N‘) { p = 0; return a; } if (a.a[px][py] == ‘S‘ || a.a[px][py] == ‘M‘) { if (a.a[px][py] == ‘S‘) { a.scnt--; if (a.scnt == 0) { p = 0; return a; } } a.a[px][py] = ‘.‘; flag=1; } } if(flag) { p=1; return a; } } else { for (int i = 0; i < 4; ++i) { int px = xx + dx[i]; int py = yy + dy[i]; if (!check(px, py)) continue; if (a.a[px][py] == ‘P‘) { if (c == ‘S‘) { a.scnt--; if (a.scnt == 0) { p = 0; return a; } } a.a[xx][yy] = ‘.‘; p = 1; return a; } } for (int i = 0; i < 4; ++i) { int px = xx + dx[i]; int py = yy + dy[i]; if (!check(px, py)) continue; if (a.a[px][py] == ‘N‘) { if (c == ‘S‘) { p = 2; return a; } p = 0; return a; } } } x = xx; y = yy; } return a;}int d[MAXN];int bfs(ULL st) { int tail = 0; d[0] = 0; q[tail++] = st; mp.clear(); mp[st] = 1; for (int i = 0; i < tail; ++i) { node a = node(q[i]); REP(j,6) REP(k,8) { if (a.a[j][k] == ‘S‘ || a.a[j][k] == ‘M‘ || a.a[j][k] == ‘P‘) { for (int x = 0; x < 4; ++x) { int p; node e = move(a, j, k, dx[x], dy[x], p); if (p == 2) { return d[i] + 1; } if (p == 1) { ULL hs = geths(e.a); if (mp.find(hs) == mp.end()) { mp[hs] = 1; q[tail] = hs; d[tail++] = d[i] + 1; } } } } } } printf("tail:%d\n",tail); return -1;}int main() {// freopen("1.txt","w",stdout); bas[0] = 1; for (int i = 1; i <= 64; ++i) bas[i] = bas[i - 1] * 2; while(scanf(" %s",s[0])!=EOF){ for(int i=1;i<6;++i)scanf(" %s",s[i]); init(); ULL hs=geths(s); REP(i,6)REP(j,8)if(s[i][j]==‘S‘||s[i][j]==‘M‘||s[i][j]==‘P‘)s[i][j]=‘.‘; int ans=bfs(hs); printf("%d\n",ans); } return 0;}
HDU 5010 Get the Nut(2014 ACM/ICPC Asia Regional Xi'an Online)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。