2014
11-29

# Ice-Skating

FJ becomes interested in ice-skating these days. Every weekends, he goes to the rink in his town. The rink is a rectangle that made up of r rows and c colomns of small squares. Some of squares are damaged and skating on these squares are forbidden.

FJ is a beginner, and he can only do a sequence of k actions one after another. One action means skating forward at most l squares (Doesn’t include the square he start at) in a certain direction (Up, Down, Left and Right). Notice that he can’t skate on broken squares.

Now the problem is: Given the rink and the sequence of actions, how long can FJ skating at most.

The first line of input file is a single integer T (1 ≤ T ≤ 10) – the number of test cases. For each test case, in the first line there are 5 integers: r, c, x, y, k. The meaning of r, c and k are described as above. x and y means FJ is at the square in the x-th row (counting from the top and start from 1) and y-th colomn (counting from the left side and start from 1). Then there are r lines, describing the rink – ‘.’ means good squares, and ‘x’ means broken squares. Then there are k lines, giving the k actions in order. Each of these lines contain 2 integers: l and d, d ∈ {1, 2, 3, 4}, 1 represent upward, 2 represent left, 3 represent downward and 4 represent right.

(1 ≤ r, c ≤ 200; 1 ≤ k ≤ 200);

The first line of input file is a single integer T (1 ≤ T ≤ 10) – the number of test cases. For each test case, in the first line there are 5 integers: r, c, x, y, k. The meaning of r, c and k are described as above. x and y means FJ is at the square in the x-th row (counting from the top and start from 1) and y-th colomn (counting from the left side and start from 1). Then there are r lines, describing the rink – ‘.’ means good squares, and ‘x’ means broken squares. Then there are k lines, giving the k actions in order. Each of these lines contain 2 integers: l and d, d ∈ {1, 2, 3, 4}, 1 represent upward, 2 represent left, 3 represent downward and 4 represent right.

(1 ≤ r, c ≤ 200; 1 ≤ k ≤ 200);

1
4 5 4 1 3
..xx.
.....
...x.
.....
3 4
2 1
2 2

6

Hint
For the sample input, FJ can skate in this way:



/*
* File: NOI2005waltz.cpp
* Author: hust_boys
* Created on 2010��10��12��, ����10:33
*/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 201

using namespace std;

char Map[N][N];
int f[2][N][N], n, m;

void init(int x, int y) {
for (int i = 0; i < n; ++i) {
scanf("%s", Map[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
f[0][i][j] = -1;
}
}
f[0][x - 1][y - 1] = 0;
}

struct Queue {
int id[N], w[N], left, right;

void init() {
left = right = 0;
}

bool empty() {
return left == right;
}

void insert(int pos, int v, int len) {
if (left < right && abs(id[left] - pos) > len) {
++left;
}
if (v == -1) {
return;
}
while (left < right) {
int p = right - 1;
if (w[p] + abs(id[p] - pos) > v) {
break;
}
--right;
}
id[right] = pos, w[right] = v;
++right;
}

int left_id() {
return id[left];
}
} que;

void DP(int k, int len, int d) {
switch (d) {

case 1:
for (int j = 0; j < m; ++j) {
que.init();
for (int i = n - 1; i >= 0; --i) {
que.insert(i, f[1 - k][i][j], len);
if (Map[i][j] == 'x') {
que.init();
}
if (que.empty()) {
f[k][i][j] = -1;
} else {
f[k][i][j] = f[1 - k][que.left_id()][j] + que.left_id() - i;
}
}
}
break;
case 3:
for (int j = 0; j < m; ++j) {
que.init();
for (int i = 0; i < n; ++i) {
que.insert(i, f[1 - k][i][j], len);
if (Map[i][j] == 'x') {
que.init();
}
if (que.empty()) {
f[k][i][j] = -1;
} else {
f[k][i][j] = f[1 - k][que.left_id()][j] + i - que.left_id();
}
}
}
break;
case 2:
for (int i = 0; i < n; ++i) {
que.init();
for (int j = m - 1; j >= 0; --j) {
que.insert(j, f[1 - k][i][j], len);
if (Map[i][j] == 'x') {
que.init();
}
if (que.empty()) {
f[k][i][j] = -1;
} else {
f[k][i][j] = f[1 - k][i][que.left_id()] + que.left_id() - j;
}
}
}
break;
case 4:
for (int i = 0; i < n; ++i) {
que.init();
for (int j = 0; j < m; ++j) {
que.insert(j, f[1 - k][i][j], len);
if (Map[i][j] == 'x') {
que.init();
}
if (que.empty()) {
f[k][i][j] = -1;
} else {
f[k][i][j] = f[1 - k][i][que.left_id()] + j - que.left_id();
}
}
}
break;
}
}

int main(int argc, char** argv) {
int x, y, tot, T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d%d", &n, &m, &x, &y, &tot);
init(x, y);
for (int i = 1; i <= tot; ++i) {
int len, d;
scanf("%d%d", &len, &d);
DP(i % 2, len, d);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ans = (ans < f[tot % 2][i][j] ? f[tot % 2][i][j] : ans);
}
}
printf("%d\n", ans);
}
return 0;
}

1. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。