学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2653

http://acm.hdu.edu.cn/showproblem.php?pid=2579

题目的意思都很简单，主要写这篇博客的原因是学会了状态标记这个技巧，对于迷宫各种类 的，每个位置可以多次走过 的且对于每个格子的状态较少，可以多加一维来进行状态标记。

2653，对于每个位置，其余数就是一个状态。。比较简单。。一开始，自己想的各种，都是错的。。后来有了这个个技巧，马上就AC了。。这绝对的一个很好的技巧

Code：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 85;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, t, p, bx, by;
char map[N][N];
bool vis[N][N][N];//mark for the states...
struct Node{
    int x, y;
    int ener, step;
    Node(){ }
    Node(int a, int b, int c, int d){
        x = a; y = b;
        ener = c; step = d;
    }
    bool friend operator < (Node X, Node Y){
        if(X.step > Y.step) return true;
        return false;
    }
};

void bfs(){
    memset(vis, 0, sizeof(vis));
    priority_queue<Node> q;
    q.push(Node(bx, by, p, 0));
    vis[bx][by][p] = true;
    while(!q.empty()){
        Node tmp1 = q.top(), tmp2;
        if(tmp1.step > t) break;
        q.pop();
        if(map[tmp1.x][tmp1.y] == 'L'){
            if(tmp1.step <= t) printf("Yes, Yifenfei will kill Lemon at %d sec.\n", tmp1.step);
            else puts("Poor Yifenfei, he has to wait another ten thousand years.");
            return ;
        }
//        printf("%d %d %d %d\n", tmp1.x, tmp1.y, tmp1.step, tmp1.ener);
        for(int i = 0; i < 4; i ++){
            tmp2.x = tmp1.x + dx[i]; tmp2.y = tmp1.y + dy[i];
            if(tmp2.x < 1 || tmp2.x > n || tmp2.y < 1 || tmp2.y > m || map[tmp2.x][tmp2.y] == '#') continue;
            if(tmp1.ener != 0 && !vis[tmp2.x][tmp2.y][tmp1.ener - 1]){ // fly
                tmp2.ener = tmp1.ener - 1;
                tmp2.step = tmp1.step + 1;
                vis[tmp2.x][tmp2.y][tmp2.ener] = true;
                q.push(tmp2);
            }// walk..
            if(map[tmp1.x][tmp1.y] != '@' && map[tmp2.x][tmp2.y] != '@' && !vis[tmp2.x][tmp2.y][tmp1.ener]){
                tmp2.ener = tmp1.ener;
                tmp2.step = tmp1.step + 2;
                vis[tmp2.x][tmp2.y][tmp2.ener] = true;
                q.push(tmp2);
            }
        }
    }
    puts("Poor Yifenfei, he has to wait another ten thousand years.");
    return ;
}
int main(){// you can step on the same gird if you have the different power
    int k = 0;
//    freopen("11.txt", "r", stdin);
    while(~scanf("%d %d %d %d", &n, &m, &t, &p)){
        getchar();
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                scanf("%c", &map[i][j]);
                if(map[i][j] == 'Y') bx = i, by = j;
            }
            getchar();
        }
        printf("Case %d:\n", ++ k);
        bfs();
    }
    return 0;
}

另外一道题，也是很easy的题目，同样，状态很少。。

Code：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 105;
const int M = 15;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
char map[N][N];
bool vis[N][N][M];
int n, m, k, bx, by;
struct Node{
    int x, y;
    int step;
    Node(){ }
    Node(int a, int b, int c){
        x = a;
        y = b;
        step = c;
    }
    bool friend operator < (Node X, Node Y){
        if(X.step > Y.step) return true;
        return false;
    }
};

void bfs(){
    memset(vis, 0, sizeof(vis));
    priority_queue<Node> q;
    q.push(Node(bx, by, 0));
    vis[bx][by][0] = true;
    while(!q.empty()){
        Node tmp1 = q.top(), tmp2;
        q.pop();
        if(map[tmp1.x][tmp1.y] == 'G'){
            printf("%d\n", tmp1.step);
            return ;
        }
//        printf("%d %d %d\n", tmp1.x, tmp1.y, tmp1.step);
        for(int i = 0; i < 4; i ++){
            tmp2.x = tmp1.x + dx[i]; tmp2.y = tmp1.y + dy[i];
            if(tmp2.x < 1 || tmp2.x > n || tmp2.y < 1 || tmp2.y > m) continue;
            if(map[tmp2.x][tmp2.y] == '#' && (tmp1.step + 1) % k == 0){
                tmp2.step = tmp1.step + 1;
                q.push(tmp2);
            }
            else if(map[tmp2.x][tmp2.y] != '#' && !vis[tmp2.x][tmp2.y][(tmp1.step + 1) % k])
            {
                    tmp2.step = tmp1.step + 1;
                    vis[tmp2.x][tmp2.y][tmp2.step % k] = true;
                    q.push(tmp2);
            }
        }
    }
    puts("Please give me another chance!");
    return ;
}

int main(){
//    freopen("1.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%d %d %d", &n, &m, &k);
        getchar();
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                scanf("%c", &map[i][j]);
                if(map[i][j] == 'Y') bx = i, by = j;
            }
            getchar();
        }
        bfs();
    }
    return 0;
}

应该尽快吧这几十道题目A了。。留给我们的时间确实已经不多了。。