hdu3533 (bfs + 模拟)

不要忘记 (vis) 数组..

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 105;

int n, m, k, d;

bool vis[maxn][maxn][1005];
bool a[maxn][maxn];

struct {
    char dir;
    int t, v;
}c[maxn][maxn];

struct Node{
    int x, y, t;
};

int dx[5] = {0, 0, 1, -1, 0};
int dy[5] = {1, -1, 0, 0, 0};

bool check(int t, int x, int y){
    for(int i = x - 1 ; i >= 0 ; --i){
        if(a[i][y]){
            if((x - i) % c[i][y].v != 0 || c[i][y].dir != 'S' || x - i > t) break;
            if((t - (x - i) / c[i][y].v) % c[i][y].t == 0) return false;
            break;
        }
    }
    
    for(int i = x + 1 ; i <= n ; ++i){
        if(a[i][y]){
            if((i - x) % c[i][y].v != 0 || c[i][y].dir != 'N' || i - x > t) break;
            if((t - (i - x) / c[i][y].v) % c[i][y].t == 0) return false;
            break;
        }
    }
    
    for(int i = y - 1 ; i >= 0 ; --i){
        if(a[x][i]){
            if((y - i) % c[x][i].v != 0 || c[x][i].dir != 'E'|| y - i > t) break;
            if((t - (y - i) / c[x][i].v) % c[x][i].t == 0) return false;
            break;
        }
    }
    
    for(int i = y + 1 ; i <= m ; ++i){
        if(a[x][i]){
            if((i - y) % c[x][i].v != 0 || c[x][i].dir != 'W' || i - y > t) break;
            if((t - (i - y) / c[x][i].v) % c[x][i].t == 0) return false;
            break;
        }
    }
    
    return true;
}

void bfs(){
    queue<Node> q;
    Node u, v; u.x = 0, u.y = 0, u.t = 0;
    q.push(u);
    
    while(!q.empty()){
        u = q.front(); q.pop();
        int x = u.x, y = u.y, t = u.t;
        
        if(vis[x][y][t]) continue;
        vis[x][y][t] = true;
        
        if(x == n && y == m){
            printf("%d
", u.t);
            return;
        }
        
        for(int i = 0 ; i < 5 ; ++i){
            int xx = u.x + dx[i], yy = u.y + dy[i];
            if(xx >= 0 && xx <= n && yy >= 0 && yy <= m && !a[xx][yy] && u.t + 1 <= d && check(u.t + 1, xx, yy)){//
                v.x = xx, v.y = yy, v.t = u.t + 1;
                q.push(v);
            }
        }
    }
    printf("Bad luck!
");
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
    while(cin>>n>>m>>k>>d){
    	memset(vis, 0, sizeof(vis));
    	memset(c, 0, sizeof(c));
    	memset(a, 0, sizeof(a));
    	
        for(int i = 1 ; i <= k ; ++i){
        	char s;
            int t, v, x, y;
            cin>>s>>t>>v>>x>>y;
  
            a[x][y] = true;
            c[x][y].dir = s; c[x][y].t = t, c[x][y].v = v;
        }
        
        bfs();
    }
    
    return 0;
}