https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=951
题意:给出一个由大小写字母组成的二维maze…给出k个询问。每个询问一个单词。问能否在maze中找到这个单词。不区分大小写。输出开头字母的坐标(从1开始)。如果有多组输出最上面的。如果还有多组,输出最左边的。数据保证至少有一组。
思路:直接找就好了。。。坑的地方是。。。格式。。数据组数之后会有一个空行。然后每两组读入数据之间会有一个空行。。输出的时候每两组数据之间也有一个空行。
我因为一直多输出了一个空行一直wa QAQ
=
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 |
/* *********************************************** Author :111qqz Created Time :2016年01月21日 星期四 14时52分51秒 File Name :code/uva/10010.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=80; int n,m; char maze[N][N]; string spa; int k; char target[100]; char nouse[55]; bool hang( int x,int y,char tar[]) { int len = strlen(tar); // cout<<"tar:"<<tar<<endl; if (y+len-1>=m) return false; int cnt = 0 ; for ( int j = y ; j < y+len; j++) { if (maze[x][j]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool rhang( int x,int y,char tar[]) { int len = strlen(tar); if (y-len+1<0) return false; int cnt = 0 ; for ( int j = y ; j >=y-len+1 ; j-- ) { if (maze[x][j]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool lie( int x,int y,char tar[]) { int len = strlen(tar); int cnt = 0 ; if (x+len-1>=n) return false; for ( int i = x ; i < x + len ; i++) { if (maze[i][y]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool rlie( int x,int y,char tar[]) { int len = strlen(tar); int cnt = 0 ; if (x-len+1<0) return false; for ( int i = x ; i>=x-len+1 ; i --) { if (maze[i][y]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool zx( int x,int y, char tar[]) { int len = strlen(tar); int cnt = 0; if (y+len-1>=m||x+len-1>=n) return false; for ( int i = x ; i < x+len ; i++) { if (maze[i][y+cnt]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool rzx ( int x,int y,char tar[]) { int len = strlen(tar); int cnt = 0 ; if (y-len+1<0||x-len+1<0) return false; for ( int i = x ; i >= x-len+1 ; i--) { if (maze[i][y-cnt]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool fx( int x,int y,char tar[]) { int len = strlen(tar); int cnt = 0 ; if (y-len+1<0||x+len-1>=m) return false; for ( int i = x ; i < x+len ; i++) { if (maze[i][y-cnt]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } bool rfx( int x,int y,char tar[]) { int len = strlen(tar); int cnt = 0 ; if (x-len+1<0||y+len-1>=m) return false; for ( int j = y ; j < y+len ; j++) { if (maze[x-cnt][y]!=tar[cnt]) return false; cnt++; } cout<<x+1<<" "<<y+1<<endl; return true; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif int T; scanf("%d",&T); //getline(cin,spa); scanf("*%s",nouse); while (T--) { scanf("%d%d",&n,&m); //习惯用n表示行。。。与题目相反。 for ( int i = 0 ;i < n ; i++) { scanf("%s",maze[i]); for ( int j = 0 ; j < m ; j++) { maze[i][j]=toupper(maze[i][j]); } } //for ( int i = 0 ; i < n ; i++) cout<<maze[i]<<endl; scanf("%d",&k); while (k--) { scanf("%s",target); int len ; len = strlen(target); bool ok = false; for ( int i = 0 ;i < len ; i++) target[i] = toupper(target[i]); // cout<<"target:"<<target<<endl; for ( int i = 0 ; i < n ;i++) { for ( int j = 0 ; j < m ; j++) { 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)) { ok = true; break; } } if (ok) break; } } if (T!=0) { scanf("*%s",nouse); cout<<endl; } } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!