uva 10010 - Where's Waldorf?
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=951 题意:给出一个由大小写字母组成的二维maze...给出k个询问。每个询问一个单词。问能否在maze中找到这个单词。不区分大小写。输出开头字母的坐标(从1开始)。如果有多组输出最上面的。如果还有多组,输出最左边的。数据保证至少有一组。 思路:直接找就好了。。。坑的地方是。。。格式。。数据组数之后会有一个空行。然后每两组读入数据之间会有一个空行。。输出的时候每两组数据之间也有一个空行。
我因为一直多输出了一个空行一直wa QAQ
=
/* ***********************************************
Author :111qqz
Created Time :2016年01月21日 星期四 14时52分51秒
File Name :code/uva/10010.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=80;
7int n,m;
8char maze[N][N];
9string spa;
10int k;
11char target[100];
12char nouse[55];
1bool hang( int x,int y,char tar[])
2{
3 int len = strlen(tar);
4 // cout<<"tar:"<<tar<<endl;
5 if (y+len-1>=m) return false;
6 int cnt = 0 ;
7 for ( int j = y ; j < y+len; j++)
8 {
9 if (maze[x][j]!=tar[cnt])
10 return false;
11 cnt++;
12 }
1 cout<<x+1<<" "<<y+1<<endl;
2 return true;
3}
4bool rhang( int x,int y,char tar[])
5{
6 int len = strlen(tar);
7 if (y-len+1<0) return false;
8 int cnt = 0 ;
9 for ( int j = y ; j >=y-len+1 ; j-- )
10 {
1 if (maze[x][j]!=tar[cnt])
2 return false;
3 cnt++;
4 }
5 cout<<x+1<<" "<<y+1<<endl;
6 return true;
7}
1bool lie( int x,int y,char tar[])
2{
3 int len = strlen(tar);
4 int cnt = 0 ;
5 if (x+len-1>=n) return false;
6 for ( int i = x ; i < x + len ; i++)
7 {
8 if (maze[i][y]!=tar[cnt])
9 return false;
10 cnt++;
11 }
1 cout<<x+1<<" "<<y+1<<endl;
2 return true;
3}
1bool rlie( int x,int y,char tar[])
2{
3 int len = strlen(tar);
4 int cnt = 0 ;
5 if (x-len+1<0) return false;
6 for ( int i = x ; i>=x-len+1 ; i --)
7 {
8 if (maze[i][y]!=tar[cnt]) return false;
9 cnt++;
10 }
11 cout<<x+1<<" "<<y+1<<endl;
12 return true;
}
1bool zx( int x,int y, char tar[])
2{
3 int len = strlen(tar);
4 int cnt = 0;
5 if (y+len-1>=m||x+len-1>=n) return false;
1 for ( int i = x ; i < x+len ; i++)
2 {
3 if (maze[i][y+cnt]!=tar[cnt]) return false;
4 cnt++;
5 }
6 cout<<x+1<<" "<<y+1<<endl;
7 return true;
}
1bool rzx ( int x,int y,char tar[])
2{
3 int len = strlen(tar);
4 int cnt = 0 ;
5 if (y-len+1<0||x-len+1<0) return false;
6 for ( int i = x ; i >= x-len+1 ; i--)
7 {
8 if (maze[i][y-cnt]!=tar[cnt]) return false;
9 cnt++;
10 }
11 cout<<x+1<<" "<<y+1<<endl;
12 return true;
13}
14bool fx( int x,int y,char tar[])
15{
16 int len = strlen(tar);
17 int cnt = 0 ;
18 if (y-len+1<0||x+len-1>=m) return false;
1 for ( int i = x ; i < x+len ; i++)
2 {
3 if (maze[i][y-cnt]!=tar[cnt]) return false;
4 cnt++;
5 }
6 cout<<x+1<<" "<<y+1<<endl;
7 return true;
8}
9bool rfx( int x,int y,char tar[])
10{
11 int len = strlen(tar);
12 int cnt = 0 ;
13 if (x-len+1<0||y+len-1>=m) return false;
1 for ( int j = y ; j < y+len ; j++)
2 {
3 if (maze[x-cnt][y]!=tar[cnt]) return false;
4 cnt++;
5 }
6 cout<<x+1<<" "<<y+1<<endl;
7 return true;
8}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
6 int T;
7 scanf("%d",&T);
8 //getline(cin,spa);
9 scanf("*%s",nouse);
10 while (T--)
11 {
12 scanf("%d%d",&n,&m); //习惯用n表示行。。。与题目相反。
13 for ( int i = 0 ;i < n ; i++)
14 {
15 scanf("%s",maze[i]);
16 for ( int j = 0 ; j < m ; j++)
17 {
18 maze[i][j]=toupper(maze[i][j]);
19 }
20 }
//for ( int i = 0 ; i < n ; i++) cout<<maze[i]<<endl;
scanf("%d",&k);
1 while (k--)
2 {
3 scanf("%s",target);
4 int len ;
5 len = strlen(target);
6 bool ok = false;
7 for ( int i = 0 ;i < len ; i++) target[i] = toupper(target[i]);
8 // cout<<"target:"<<target<<endl;
9 for ( int i = 0 ; i < n ;i++)
10 {
11 for ( int j = 0 ; j < m ; j++)
12 {
13 if( rzx(i,j,target)||rlie(i,j,target)||rfx(i,j,target)||rhang(i,j,target)||hang(i,j,target)||fx(i,j,target)||lie(i,j,target)||zx(i,j,target))
14 {
15 ok = true;
16 break;
17 }
18 }
19 if (ok) break;
20 }
21 }
1 if (T!=0)
2 {
3 scanf("*%s",nouse);
4 cout<<endl;
5 }
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}