hdu 5025 Saving Tang Monk
状态压缩的BFS，一般适用于每种状态能在有限空间内表示的情况
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int MAXN = 101; int n, m; bool vis[MAXN][MAXN][10][35]; int snake[10][2], csnk; char da[MAXN][MAXN]; int Kong[2], Tang[2], dir[4][2] = {0,1, 0,-1, -1,0, 1,0}; struct _node { int x, y, nk, snk, cost; _node (){} _node (int ix, int iy, int ink, int isnk, int icost) { x = ix; y = iy; nk = ink; snk = isnk; cost = icost; } }; queue<_node> mmp; int solve(int x, int y) { char cc; int res = 0x3f3f3f3f; _node tp(x,y,0,0,0); mmp.push(tp); while (!mmp.empty()) { tp = mmp.front(); mmp.pop(); x = tp.x, y = tp.y; if (x==Tang[0] && y==Tang[1] && tp.nk==m) res = min(res, tp.cost); if (vis[x][y][tp.nk][tp.snk]) continue; vis[x][y][tp.nk][tp.snk] = 1; for (int i = 0; i< 4; ++i) { int xx = x+dir[i][0], yy = y+dir[i][1]; if (xx>=0&&xx<n&&yy>=0&&yy<n && da[xx][yy]!='#') { cc = da[xx][yy]; _node ad(xx,yy,tp.nk,tp.snk,tp.cost+1); if (cc >= '1' && cc <='9') { if (ad.nk+1 == cc-'0') { ad.nk += 1; } } else if (cc>=0 && cc<csnk) { if ((tp.snk & (1<<cc))==0) { ad.snk = ad.snk|(1<<cc), ++ad.cost; } } if (!vis[ad.x][ad.y][ad.nk][ad.snk]) mmp.push(ad); } } } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE while (scanf("%d%d", &n, &m) != EOF && (n+m)) { csnk = 0; memset(vis, 0, sizeof vis); for (int i = 0; i< n; ++i) scanf("%s", da[i]); for (int i = 0; i< n; ++i) { for (int j = 0; j< n; ++j) { switch (da[i][j]) { case 'K': Kong[0]=i, Kong[1]=j; break; case 'T': Tang[0]=i, Tang[1]=j; break; case 'S': da[i][j]= char(csnk++); break; } } } int res = solve(Kong[0], Kong[1]); if (res == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", res); } return 0; }
hdu 5031 Lines
根据题意，必然有解。那么枚举每个点和过该点的直线，DFS后更新结果
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <set> using namespace std; const int MAXN = 55; int n, m, da[MAXN][MAXN], res; set<double> mmp; void dfs(int cnt, int last) { if (cnt >= res) return; if (!last) { res = min(res, cnt); return; } int flg = 1; for (int x = 0; x<= n && flg; ++x) for (int y = 0; y<= m && flg; ++y) { if (da[x][y] == 0) continue; flg = 0; if (x == 0) { int k; for (k = 0; k<= n; ++k) if (!da[k][y]) break; if (k == n+1) { for (k = 0; k<= n; ++k) --da[k][y]; dfs(cnt+1, last-n-1); for (k = 0; k<= n; ++k) ++da[k][y]; } } if (y == 0) { int k = 0; for (; k<= m; ++k) if (!da[x][k]) break; if (k == m+1) { for (k = 0; k<= m; ++k) --da[x][k]; dfs(cnt+1, last-m-1); for (k = 0; k<= m; ++k) ++da[x][k]; } } mmp.clear(); for (int a = x+1; a<= n; ++a) { for (int b = 0; b <= m; ++b) { if (b == y || da[a][b] == 0) continue; int p = a-x, q = b-y; if (mmp.find(double(p)/q) != mmp.end()) continue; mmp.insert(double(p)/q); int o = 1; while (x+p*o>= 0 && x+p*o <=n && y+q*o>=0 && y+q*o <= m && da[x+p*o][y+q*o]) ++o; if (x+p*o>= 0 && x+p*o <=n && y+q*o>=0 && y+q*o <= m) continue; if (x-p>= 0 && x-p <=n && y-q>=0 && y-q <= m) continue; if (o < 3) continue; for (o = 1; x+p*o>= 0 && x+p*o <=n && y+q*o>=0 && y+q*o <= m; ++o) --da[x+p*o][y+q*o]; --da[x][y]; dfs(cnt+1, last-o); ++da[x][y]; for (o = 1; x+p*o>= 0 && x+p*o <=n && y+q*o>=0 && y+q*o <= m; ++o) ++da[x+p*o][y+q*o]; } } } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE int t, sm; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); sm = 0; for (int i = 0; i<= n; ++i) { for (int j = 0; j<= m; ++j) { scanf("%d", &da[i][j]); sm += da[i][j]; } } res = min(14, sm/3); dfs(0, sm); printf("%d\n", res); } return 0; }