首页 > ACM题库 > HDU-杭电 > HDU 3620-Ice-Skating[解题报告]HOJ
2014
11-29

HDU 3620-Ice-Skating[解题报告]HOJ

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: Heroes of Might and Magic

/*
 * 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选项是不对的。