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:WA的试试

Posted by sos_dan at 2016-10-15 15:38:28 on Problem 3669
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:
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