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 makuiyu at 2013-12-27 15:54:52 on Problem 3620
In Reply To:大忌 WA的同志们一定要注意 Posted by:vince4053040 at 2010-01-29 23:02:40
> for(i = 1; i <= N; i ++)           //大忌   不是(i = 0; i < N; i  ++)
> 		for(j = 1; j <= M; j ++)
> 
> 
> 拿这组数据测测就知道了  
> sample input:
> 1 1 1
> 1 1
> 
> 
> 答案是 1 不是 0

对每个水坑BFS,没有用到上面的循环。。。

#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define N 110

using namespace std;

int map[N][N], row[N*N], column[N*N];
int n, m, index, maxi=0;
int move[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void BFS(int r, int c)
{
    if(map[r][c] == -1)
    {
        map[r][c] = index++;
        if(map[r][c] > maxi)
            maxi = map[r][c];
        for(int i=0; i<4; ++i)
        {
            int tr = r + move[i][0];
            int tc = c + move[i][1];
            if(tr>0 && tr<=n && tc>0 && tc<=m)
                BFS(tr, tc);
        }
    }
}

int main()
{
    int i, k;
    memset(map, 0, sizeof(map));
    scanf("%d %d %d", &n, &m, &k);
    for(i=0; i<k; ++i)
    {
        scanf("%d %d", &row[i], &column[i]);
        map[row[i]][column[i]] = -1;
    }
    for(i=0; i<k; ++i)
    {
        index = 1;
        BFS(row[i], column[i]);
    }
    printf("%d\n", maxi);
    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