记录编号	569660	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-03-14 20:45:52	内存使用	0.00 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 20;
const int maxk = 2050;
const int INF = 0x3f3f3f3f;
int n,m,p;
int fx[] = {0 , -1 , 0 , 1},fy[] = {-1 , 0 , 1 , 0};
int val[maxn][maxn];
int valid[maxn][maxn][maxn][maxn];
int dis[maxn][maxn][maxk];
bool vis[maxn][maxn][maxk];
struct node {
    int x,y,z;
    node() {
        x = y = z = 0;
    }
    node(int x,int y,int z):x(x),y(y),z(z){}
};
queue<node> q;
int BFS() {
    memset(vis , false , sizeof(vis));
    memset(dis , 0x3f , sizeof(dis));
    dis[1][1][val[1][1]] = 0;
    vis[1][1][val[1][1]] = true;
    q.push(node(1 , 1 , val[1][1]));
    while(!q.empty()) {
        int x = q.front().x,y = q.front().y,z = q.front().z;
        q.pop();
        if(x == n&&y == m) {
            return dis[x][y][z];
        }
        for(int k = 0;k < 4;++ k) {
            int nx = x + fx[k],ny = y + fy[k];
            int nval = val[nx][ny];
            if(nx < 1||ny < 1||nx > n||ny > m)continue ;
            if(vis[nx][ny][z | nval])continue ;
            if(!valid[x][y][nx][ny])continue ;
            if(valid[x][y][nx][ny] == -1) {
                vis[nx][ny][z | nval] = true;
                dis[nx][ny][z | nval] = dis[x][y][z] + 1;
                q.push(node(nx , ny , z | nval));
            }
            else if(z & (1 << valid[x][y][nx][ny])) {
                vis[nx][ny][z | nval] = true;
                dis[nx][ny][z | nval] = dis[x][y][z] + 1;
                q.push(node(nx , ny , z | nval));
            }
        }
    }
    return INF;
}
int main() {
    freopen("rescue.in","r",stdin);
    freopen("rescue.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    memset(valid , -1 , sizeof(valid));
    int Q;
    scanf("%d",&Q);
    while(Q --) {
        int a,b,c,d,g;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&g);
        valid[a][b][c][d] = valid[c][d][a][b] = g;
    }
    scanf("%d",&Q);
    while(Q --) {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        val[x][y] |= 1 << z;
    }
    int ans = BFS();
    printf("%d\n",ans == INF ? -1 : ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}