UVA - 10010
Description
Given a m by n grid of letters, ( ), and a list of words, find the location in the grid at which InputThe input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input begins with a pair of integers, m followed by n, in decimal notation on a single line. OutputFor each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output. The integers must be separated by a single space. The first integer is the line in the grid where the first letter of the given Sample Input1 8 11 abcDEFGhigg hEbkWalDork FtyAwaldORm FtsimrLqsrc byoArBeDeyv Klcbqwikomk strEBGadhrb yUiqlxcnBjf 4 Waldorf Bambi Betty Dagbert Sample Output2 5 2 3 1 2 7 8 Miguel Revilla 2000-08-22 Input Output Sample Input Sample Output Hint Source Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 6. String Processing ::Ad
Hoc String Processing Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 1. Elementary Problem Solving ::String Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: String Processing :: String Matching ::In 2D Grid Root :: Programming Challenges (Skiena & Revilla) :: Chapter 3 Root :: Prominent Problemsetters :: Gordon V. Cormack Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: String Processing :: String Matching ::In 2D Grid |
题目大意:
先告诉你有多少组数据
然后再下面有多组数据
先读入n,m
再读入一个n*m的表
再读入k
下面有k个单词
你要在n*m的表里,找出k个单词的位置。
所以你只要输出的是一个字母的位置就OK了。
代码:
# include<cstdio> # include<iostream> # include<cstdlib> # include<cstring> using namespace std; char s[50][50]; char ob[50]; int len; int n,m; int d[8][2] = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}}; void init() { cin>>n>>m; getchar(); for ( int i = 0;i < n;i++ ) { for ( int j = 0;j < m;j++ ) { cin>>s[i][j]; s[i][j] = tolower(s[i][j]); } } } int dfs ( int x,int y ) { int k; int xx = x; int yy = y; for ( int l = 0;l < 8;l++ ) { for ( k = 0;k < len;k++ ) { if ( s[xx][yy]==ob[k]&&xx>=0&&xx<n&&yy>=0&&yy<m ) { xx+=d[l][0]; yy+=d[l][1]; } else break; } if ( k == len ) return 1; } return 0; } void find() { int flag = 0; int i,j; for ( i = 0;i < n;i++ ) { for ( j = 0;j < m;j++ ) { if ( dfs(i,j) ) { cout<<i+1<<" "<<j+1<<endl; flag = 1; break; } } if ( flag ) break; } } void solve() { int tt;cin>>tt; getchar(); while ( tt-- ) { gets(ob); len = strlen(ob); for ( int i = 0;i < len;i++ ) ob[i] = tolower(ob[i]); find(); } } int main(void) { int t;cin>>t; while ( t-- ) { init(); solve(); if ( t )cout<<endl; } return 0; }