Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:实在找不到错误. __ 找到了(ny = tx + dy[k];)

Posted by retown at 2019-07-03 02:19:03 on Problem 3669
In Reply To:实在找不到错误 Posted by:retown at 2019-07-03 02:10:10
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

#define INF 1000000
typedef pair<int, int> P;
int maze[320][320];
int di_t[320][320];
int dx[5] = {1, 0, -1, 0, 0}, dy[5] = {0, 1, 0, -1, 0}; 
struct me{
	int x;
	int y;
	int t;
};


vector<me> mete;

int bfs() {
	queue<P> que;
	if (maze[0][0] == 0) return -1;
	que.push(P(0, 0)); //start
	while (que.size()) {
		P p = que.front(); que.pop();
		int px = p.first, py = p.second;
		if (maze[px][py] == INF)
				return di_t[px][py];
		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i], ny = py + dy[i];
			if (0 <= nx && 0 <= ny && (di_t[px][py] + 1) < maze[nx][ny] && di_t[nx][ny] == 0) {
					que.push(P(nx, ny));
					di_t[nx][ny] = di_t[px][py] + 1;
			}
		}
	}
	return -1;
}

int main() {
	int m;
	while (cin >> m) {
		mete.clear();
		for (int i = 1; i <= m; i++) {
			me tmp;
			cin >> tmp.x >> tmp.y >> tmp.t;
			mete.push_back(tmp);
		}
		for (int i = 0; i < 320; i++) {
			for (int j = 0; j < 320; j++) {
				maze[i][j] = INF;
				di_t[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++) {
			int tx = mete[i].x, ty = mete[i].y, tt = mete[i].t;
			for (int k = 0; k < 5; k++) {
				int nx = tx + dx[k], ny = ty + dy[k];
				if (nx >= 0 && ny >= 0 && maze[nx][ny] > tt)
					maze[nx][ny] = tt;
			}
		}
		int res = bfs();
		cout << res << endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator