Ural 1099 Work Scheduling

时间:2020-12-15 16:10:29

题意:一个矩阵上面有0~9的数字,可以从任意一个格子出发,每次根据格子上的数字会前进到另一个格子(或原地不动),现在给出q个数位串,问是否有走法可以取出这个串(走到格子上的时候可以不取)。

思路:发现每个点的出度至多为1,那么可以预处理出走到这个格子后取某个数字最近的格子是哪个(f[i][j][0-9]),然后用队列存下开头,在做一遍贪心就可以了

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
int cnt,sz=,f[*][],c[][],id[][],vis[][],n,m,a[],b[],ans[*],d[*];
int read(){
char ch=getchar();int f=,t=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void dfs(int x,int y){
int dx=x+a[c[x][y]],dy=y+b[c[x][y]];
if (dx<||dx>n||dy<||dy>m) f[id[x][y]][c[x][y]]=id[x][y];
else{
f[id[x][y]][c[x][y]]=id[dx][dy];
if (!vis[dx][dy]) {vis[dx][dy]=;dfs(dx,dy);}
for (int i=;i<=;i++)
if (i!=c[x][y])
f[id[x][y]][i]=f[id[dx][dy]][i];
}
}
int main(){
n=read();m=read();int T=read();cnt=;
for (int i=;i<=n;i++){
char s[];
scanf("%s",s+);
for (int j=;j<=m;j++){
c[i][j]=s[j]-'';id[i][j]=++cnt;d[cnt]=c[i][j];
     }
}
   char s[1000005];
for (int i=;i<=;i++)
a[i]=read(),b[i]=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (!vis[i][j]){
vis[i][j]=;
ans[++sz]=id[i][j];
dfs(i,j);
}while (T--){
scanf("%s",s+);bool flag=false;
for (int i=;i<=sz;i++){
int x=ans[i];
for (int j=;j<=strlen(s+);j++){
x=f[x][s[j]-''];if (x<=) break;
}
if (x>) {flag=true;break;}
}
if (flag) printf("YES\n");else printf("NO\n");
}
}