Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:WA的试试In Reply To:Re:WA的试试 Posted by:3435973836 at 2016-02-18 20:35:17 我用这数据跑出来是13,但是还是wa,是啥情况啊 #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <string> #include <cstring> #include <queue> #define INF 10001 using namespace std; const int MAX_N = 303; int board[MAX_N][MAX_N]; int vis[MAX_N][MAX_N]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; struct Point { int x; int y; int t; Point(int x, int y, int t):x(x), y(y), t(t) { } }; int M; bool issafe(int x, int y) { bool result; result = board[x][y] == INF && board[x + 1][y] == INF && board[x][y + 1]== INF; if (x - 1 >= 0) result = board[x - 1][y] == INF && result; if (y - 1 >= 0) result = board[x][y - 1] == INF && result; return result; } bool isavail(int x, int y, int t) { bool result; result = board[x][y] > t + 1 && board[x + 1][y] > t + 1 && board[x][y + 1] > t + 1; if (x - 1 >= 0) result = board[x - 1][y] > t + 1 && result; if (y - 1 >= 0) result = board[x][y - 1] > t + 1 && result; return result; } void solve() { scanf("%d", &M); fill(board[0], board[0] + MAX_N * MAX_N, INF); for (int i = 0; i < M; i++) { int x, y, t; scanf("%d%d%d", &x, &y, &t); board[x][y] = t; } queue<Point> que; int startx = 0, starty = 0, startt = 0; if(!isavail(startx, starty, startt)) { printf("-1\n"); return; } else que.push(Point(startx, starty, startt)); vis[startx][starty] = 1; while (!que.empty()) { Point p = que.front(); que.pop(); if (issafe(p.x, p.y)) { printf("%d\n", p.t); return; } for (int i = 0; i < 4; i++) { int nx = p.x + dx[i], ny = p.y + dy[i]; if (isavail(nx, ny, p.t) && !vis[nx][ny]) { que.push(Point(nx, ny, p.t + 1)); vis[nx][ny] = 1; } } } printf("-1\n"); } int main() { solve(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator