E. Wilbur and Strings
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/596/problem/E
Description
Wilbur the pig now wants to play with strings. He has found an n by m table consisting only of the digits from 0 to 9 where the rows are numbered 1 to n and the columns are numbered 1 to m. Wilbur starts at some square and makes certain moves. If he is at square (x, y) and the digit d (0 ≤ d ≤ 9) is written at position (x, y), then he must move to the square (x + ad, y + bd), if that square lies within the table, and he stays in the square (x, y) otherwise. Before Wilbur makes a move, he can choose whether or not to write the digit written in this square on the white board. All digits written on the whiteboard form some string. Every time a new digit is written, it goes to the end of the current string.
Wilbur has q strings that he is worried about. For each string si, Wilbur wants to know whether there exists a starting position (x, y) so that by making finitely many moves, Wilbur can end up with the string si written on the white board.
Input
The first line of the input consists of three integers n, m, and q (1 ≤ n, m, q ≤ 200) — the dimensions of the table and the number of strings to process, respectively.
Each of the next n lines contains m digits from 0 and 9 giving the table itself.
Then follow 10 lines. The i-th of them contains the values ai - 1 and bi - 1 ( - 200 ≤ ai, bi ≤ 200), i.e. the vector that Wilbur uses to make a move from the square with a digit i - 1 in it.
There are q lines that follow. The i-th of them will contain a string si consisting only of digits from 0 to 9. It is guaranteed that the total length of these q strings won't exceed 1 000 000.
Output
For each of the q strings, print "YES" if Wilbur can choose x and y in order to finish with this string after some finite number of moves. If it's impossible, than print "NO" for the corresponding string.
Sample Input
1 1 2
0
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
0000000000000
2413423432432
Sample Output
YES
NO
HINT
题意
给你n*m的矩阵,每个矩阵里面都是0-9的数字,假设你踩到了(x,y),那么下一步就会在(x+ad,y+bd) ad和bd会给你 d是(x,y)的数值
然后你从不同的起点出发,会得到不同的字符串
然后有Q次询问,给你一个字符串,问你这个字符串是不是可能是之前的走出的字符串的子序列
题解:
暴力DP,dp[x][y][t],表示你在(x,y),你想得到字符t,你最近的一步是在哪儿
这个dp由dfs可以很容易得到
然后询问的时候,就直接暴力就好了
代码
#include<iostream>
#include<cstring>
#include<vector>
#include<stdio.h>
using namespace std; int n,m,q;
char s2[];
char s[][];
int vis[][];
int dp[*][];
int dx[];
int dy[];
vector<int> Q;
int id(int x,int y)
{
return x*m+y;
}
void dfs(int x,int y)
{
vis[x][y]=;
int t = (s[x][y]-''),p = id(x,y);
int xx = x+dx[t],yy = y+dy[t];
if(xx<||xx>=n||yy<||yy>=m)
dp[p][t]=p;
else
{
int v = id(xx,yy);
dp[p][t]=id(xx,yy);
if(vis[xx][yy]==)dfs(xx,yy);
for(int i=;i<;i++)
if(i!=t)
dp[p][i]=dp[v][i];
}
} int check(char s2[])
{
int len = strlen(s2);
for(int i=;i<Q.size();i++)
{
int x = Q[i];
for(int j=;j<len;j++)
{
x = dp[x][s2[j]-''];
if(x<)break;
}
if(x>=)return ;
}
return ;
} int main()
{
memset(dp,-,sizeof(dp));
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<n;i++)
scanf("%s",s[i]);
for(int i=;i<;i++)
scanf("%d%d",&dx[i],&dy[i]);
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(!vis[i][j])
{
dfs(i,j);
Q.push_back(id(i,j));
}
}
}
for(int i=;i<q;i++)
{
scanf("%s",s2);
if(check(s2))printf("YES\n");
else puts("NO");
}
}
Codeforces Round #331 (Div. 2) E. Wilbur and Strings dfs乱搞的更多相关文章
-
Codeforces Round #331 (Div. 2) D. Wilbur and Trees 记忆化搜索
D. Wilbur and Trees Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/596/p ...
-
Codeforces Round #331 (Div. 2)C. Wilbur and Points 贪心
C. Wilbur and Points Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/596/ ...
-
Codeforces Round #331 (Div. 2) B. Wilbur and Array 水题
B. Wilbur and Array Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/596/p ...
-
Codeforces Round #331 (Div. 2) A. Wilbur and Swimming Pool 水题
A. Wilbur and Swimming Pool Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/conte ...
-
Codeforces Round #331 (Div. 2) C. Wilbur and Points
C. Wilbur and Points time limit per test 2 seconds memory limit per test 256 megabytes input standar ...
-
Codeforces Round #331 (Div. 2) _A. Wilbur and Swimming Pool
A. Wilbur and Swimming Pool time limit per test 1 second memory limit per test 256 megabytes input s ...
-
Codeforces Round #331 (Div. 2) B. Wilbur and Array
B. Wilbur and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
Codeforces Round #Pi (Div. 2) D. One-Dimensional Battle Ships set乱搞
D. One-Dimensional Battle ShipsTime Limit: 2 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/con ...
-
水题 Codeforces Round #302 (Div. 2) A Set of Strings
题目传送门 /* 题意:一个字符串分割成k段,每段开头字母不相同 水题:记录每个字母出现的次数,每一次分割把首字母的次数降为0,最后一段直接全部输出 */ #include <cstdio> ...
随机推荐
-
自己写一个swap函数交换任意两个相同类型元素的值 对空指针的使用 字节大小的判断(二)了解原理
验证的代码: #include <stdio.h> int main(){ char c = 'z'; ) + (c << ) + () + 'a'; printf(" ...
-
特殊的css样式
在一定范围大小变化的div .div { width:auto; height:auto; min-height:100px; min-width:100px; max-height:200px; m ...
-
Eclipse开发android安装环境
好久没有用Eclipse开发android了,今天安装了一下,发现之前的andorid的sdk不能用了,然后去官网下载了一个最新的SDK,由于现在的android的官网需要FQ才能访问到,所以在这里我 ...
-
Scrapinghub | Professional Services
VShell破解版 VShell破解版 Scrapinghub | Professional Services OUR PROFESSIONAL SERVICES INCLUDE
-
Linux系统挂载点与分区的关系(转载)
计算机中存放信息的主要的存储设备就是硬盘,但是硬盘不能直接使用,必须对硬盘进行分割,分割成的一块一块的硬盘区域就是磁盘分区.在传统的磁盘管理中,将一个硬盘分为两大类分区:主分区和扩展分区.主分区是能够 ...
-
测试部署环境用到的主要linux命令
1 部署前检查开发是否上传部署文档 2 在测试组中告知大家 3 将上一版本进行备份(cp -r neiguan-tomcat/ /home/personal/backup/neiguan-tomcat ...
-
每天一道Java题[3]
问题 为什么在重写equals()方法的同时,必须重写hashCode()方法? 解答 在<每天一道Java题[2]>中,已经对hashCode()能否判断两个对象是否相等做出了解释.eq ...
-
Leetcode题解(32)
107. Binary Tree Level Order Traversal II 题目 直接代码: /** * Definition for a binary tree node. * struct ...
-
參与 Spring 4 中文文档翻译
參与 Spring 4 中文文档翻译 我们从2014年12月開始翻译Spring 4的框架文档.尽管至今已有一年,可是进度非常慢. 当中一部分原因是由于Spring 文档有1000多页,并且翻译的时候 ...
-
selenium 设置代理的话,可以使用这种方式,代码是我刚才测试过的,亲测可用
from selenium import webdriver chrome_options = webdriver.ChromeOptions() chrome_options.add_argumen ...