HDU 2821 Pusher

发布时间:2016-12-10 20:58:26 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 2821 Pusher",主要涉及到HDU 2821 Pusher方面的内容,对于HDU 2821 Pusher感兴趣的同学可以参考一下。

dfs.枚举每个点作为起点,然后四个方向移动就行。先把字符串数组转化为整数,方便判断,每次dfs前后,注意修改与恢复。 关于pile能否出界,网上很多人说什么:不能推出边界;还有人说什么:如果只有一个,就可以推出界,多了就不行,等等。但题目中明确要求: And if a whole pile is pushed outside the grid, it will be considered as cleared. 就是说可以推出界,不要人云亦云,更不要自己还没弄明白就抄了份代码发题解。。。 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<string> #include<cmath> #include<map> ///LOOP #define REP(i, n) for(int i = 0; i < n; i++) #define FF(i, a, b) for(int i = a; i < b; i++) #define FFF(i, a, b) for(int i = a; i <= b; i++) #define FD(i, a, b) for(int i = a - 1; i >= b; i--) #define FDD(i, a, b) for(int i = a; i >= b; i--) ///INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define RFI(n) scanf("%lf", &n) #define RFII(n, m) scanf("%lf%lf", &n, &m) #define RFIII(n, m, k) scanf("%lf%lf%lf", &n, &m, &k) #define RFIV(n, m, k, p) scanf("%lf%lf%lf%lf", &n, &m, &k, &p) #define RS(s) scanf("%s", s) ///OUTPUT #define PN printf("\n") #define PI(n) printf("%d\n", n) #define PIS(n) printf("%d ", n) #define PS(s) printf("%s\n", s) #define PSS(s) printf("%s ", n) #define PC(cas) printf("Game %d:\n", cas) ///OTHER #define PB(x) push_back(x) #define CLR(a, b) memset(a, b, sizeof(a)) #define CPY(a, b) memcpy(a, b, sizeof(b)) #define display(A, n, m) {REP(i, n){REP(j, m)PIS(A[i][j]);PN;}} using namespace std; typedef long long LL; typedef pair<int, int> P; const int MOD = 1000000; const int INFI = 1e9 * 2; const LL LINFI = 1e17; const double eps = 1e-6; const double pi = acos(-1.0); const int N = 55; const int M = 11111; const int move[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1}; int p[N][N], ans[M]; int n, m, num; char s[N][N], a[5] = "RLDU"; bool isclear() { REP(i, n)REP(j, m)if(p[i][j])return 0; return 1; } bool check(int x, int y) { return x >= 0 && y >= 0 && x < n && y < m; } bool dfs(int x, int y, int k) { if(isclear())return 1; int tx, ty; REP(i, 4)FF(j, 1, N) { tx = x + j * move[i][0]; ty = y + j * move[i][1]; if(!check(tx, ty))break; if(p[tx][ty]) { if(j == 1)break; int x1 = tx + move[i][0], y1 = ty + move[i][1]; int t1 = p[tx][ty], t2 = p[x1][y1]; p[x1][y1] += t1 - 1; p[tx][ty] = 0; ans[k] = i;num = k + 1; if(dfs(tx, ty, k + 1))return 1; p[x1][y1] = t2; p[tx][ty] = t1; break; } } return 0; } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); while(RII(m, n) != EOF) { CLR(p, 0); CLR(ans, -1); REP(i, n) { RS(s[i]); REP(j, m) { if(s[i][j] == '.')p[i][j] = 0; else p[i][j] = s[i][j] - 'a' + 1; } } REP(i, n)REP(j, m)if(!p[i][j]) { if(dfs(i, j, 0)) { PI(i);PI(j); REP(k, num)putchar(a[ans[k]]);puts(""); goto end; } } end: ; } return 0; }

上一篇:hdoj 1715 大菲波数
下一篇:ActiveX需要实现哪些COM接口

相关文章

关键词: HDU 2821 Pusher

相关评论