Posted on 2008-05-14 11:57
superman 閱讀(204)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1290 C++ 00:00.01 2988K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n;
7 char m[100][100];
8 struct { int x, y; } dir[8] = {
9 {-1, 0}, {-1, +1}, {0, +1}, {+1, +1},
10 {+1, 0}, {+1, -1}, {0, -1}, {-1, -1}
11 };
12
13 bool match(int x, int y, int d, string s)
14 {
15 if(d == 0 && x - s.size() + 1 < 0)
16 return false;
17 if(d == 1 && (x - s.size() + 1 < 0 || y + s.size() - 1 >= n))
18 return false;
19 if(d == 2 && y + s.size() - 1 >= n)
20 return false;
21 if(d == 3 && (x + s.size() - 1 >= n || y + s.size() - 1 >= n))
22 return false;
23 if(d == 4 && x + s.size() - 1 >= n)
24 return false;
25 if(d == 5 && (x + s.size() - 1 >= n || y - s.size() + 1 < 0))
26 return false;
27 if(d == 6 && y - s.size() + 1 < 0)
28 return false;
29 if(d == 7 && (x - s.size() + 1 < 0 || y - s.size() + 1 < 0))
30 return false;
31
32 for(int i = 1; i < s.size(); i++)
33 {
34 x += dir[d].x, y += dir[d].y;
35 if(s[i] != m[x][y])
36 return false;
37 }
38 return true;
39 }
40
41 int main()
42 {
43 int N;
44 cin >> N;
45 while(N--)
46 {
47 cin >> n;
48 for(int i = 0; i < n; i++)
49 for(int j = 0; j < n; j++)
50 cin >> m[i][j];
51
52 string word;
53 while(cin >> word)
54 {
55 if(word == "0")
56 break;
57
58 bool found = false;
59 for(int i = 0; i < n; i++)
60 for(int j = 0; j < n; j++)
61 if(word[0] == m[i][j])
62 for(int k = 0; k < 8; k++)
63 {
64 if(match(i, j, k, word))
65 {
66 cout << i + 1 << ',' << j + 1 << ' ';
67
68 if(k != 2 && k != 6)
69 cout << i + 1 + dir[k].x * (word.size() - 1) << ',';
70 else cout << i + 1 << ',';
71
72 if(k != 0 && k != 4)
73 cout << j + 1 + dir[k].y * (word.size() - 1);
74 else cout << j + 1;
75
76 found = true;
77 goto over;
78 }
79 }
80 if(found == false)
81 cout << "Not found";
82 over:
83 cout << endl;
84 }
85
86 if(N)
87 cout << endl;
88 }
89
90 return 0;
91 }
92