superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1290 - Word-Search Wonder

Posted on 2008-05-14 11:57 superman 阅读(184) 评论(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     {-10}, {-1+1}, {0+1}, {+1+1},
10     {+10}, {+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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理