| ||||||||||
| 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