Posted on 2008-03-19 12:42
superman 阅读(326)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1019 C++ 00:00.04 852K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, p;
7 bool map[101][101];
8
9 struct
10 {
11 int s, t;
12 char direction;
13 }trip[100];
14
15 bool finish;
16
17 void swap(int & a, int & b)
18 {
19 a = a ^ b;
20 b = a ^ b;
21 a = a ^ b;
22 }
23
24 inline bool canGo(int sx, int sy, int tx, int ty)
25 {
26 if(tx >= 1 && tx <= n && ty >= 1 && ty <= m);
27 else
28 return 0;
29 if(sx > tx)
30 swap(sx, tx);
31 if(sy > ty)
32 swap(sy, ty);
33 for(int i = sx; i <= tx; i++)
34 for(int j = sy; j <= ty; j++)
35 if(map[i][j])
36 return 0;
37 return 1;
38 }
39
40 void search(int x, int y, int k)
41 {
42 if(finish)
43 return;
44 if(k > p)
45 {
46 finish = 1;
47 return;
48 }
49 if(trip[k].direction == 'U')
50 {
51 for(int i = trip[k].s; i <= trip[k].t; i++)
52 if(canGo(x - 1, y, x - i, y))
53 search(x - i, y, k + 1);
54 return;
55 }
56 if(trip[k].direction == 'D')
57 {
58 for(int i = trip[k].s; i <= trip[k].t; i++)
59 if(canGo(x + 1, y, x + i, y))
60 search(x + i, y, k + 1);
61 return;
62 }
63 if(trip[k].direction == 'L')
64 {
65 for(int j = trip[k].s; j <= trip[k].t; j++)
66 if(canGo(x, y - 1, x, y - j))
67 search(x, y - j, k + 1);
68 return;
69 }
70 if(trip[k].direction == 'R')
71 {
72 for(int j = trip[k].s; j <= trip[k].t; j++)
73 if(canGo(x, y + 1, x, y + j))
74 search(x, y + j, k + 1);
75 return;
76 }
77 }
78
79 int main()
80 {
81 int N;
82 int s, t;
83 char direction;
84
85 cin >> N;
86 while(N--)
87 {
88 cin >> n >> m;
89 for(int i = 1; i <= n; i++)
90 for(int j = 1; j <= m; j++)
91 cin >> map[i][j];
92 p = 0;
93 while(1)
94 {
95 cin >> s >> t;
96 if(s == 0 && t == 0)
97 break;
98 p++;
99 trip[p].s = s;
100 trip[p].t = t;
101 cin >> trip[p].direction;
102 }
103 int ans = 0;
104 for(int i = 1; i <= n; i++)
105 for(int j = 1; j <= m; j++)
106 if(map[i][j] == 0)
107 {
108 finish = 0;
109 search(i, j, 1);
110 ans += finish;
111 }
112 cout << ans << endl;
113 }
114
115 return 0;
116 }
117