1547.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1547 on 2006-05-27 at 20:36:33 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int PN = 128;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

int n, map[PN][PN], d[PN][PN], b[PN][PN];
vector<int> nxt[PN][PN];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

int main()
{
	int p, i, j, k, l;

	while(scanf("%d %d", &n, &p) != EOF && n > 0) {
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				nxt[i][j].clear();
			}
		memset(d, 0, sizeof(d));
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				for(k = 0; k < 4; k++)
					for(l = 1; l <= p; l++) {
						int x = i+DIR[k][0]*l, y = j+DIR[k][1]*l;
						if(!legal(x, y)) break;
						else if(map[i][j] > map[x][y])
							{ nxt[i][j].push_back(x*PN+y); d[x][y]++; }
					}
		memcpy(b, map, sizeof(b));
		int stack[PN*PN], top = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(d[i][j] == 0) stack[top++] = i*PN+j;
		while(top > 0) {
			int px = stack[--top], x = px / PN, y = px % PN;
			if(px == 0) break;
			for(i = 0; i < nxt[x][y].size(); i++) {
				int o = nxt[x][y][i], ox = o / PN, oy = o % PN;
				b[ox][oy] = max(b[ox][oy], b[x][y]+map[ox][oy]);
				--d[ox][oy];
				if(d[ox][oy] == 0) stack[top++] = ox*PN+oy;
			}
		}
		printf("%d\n", b[0][0]);
	}
	
	return 0;
}