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

我哪里错了??为什么WA?? 帮忙给看看:

Posted by kikif at 2007-08-31 21:16:28 on Problem 3194
我的思路就是输入的时候将给数组编号1--(n-1)剩下的就是编号为5的点,我将其默认成为0
然后分别对编号0到n-1进行深度优先遍历,如果遍历一次还有编号为cur的没有被遍历到,直接退出,
我测试了所有的数据都是正确的,为什么WA呢?

#include <iostream>
#include <fstream>
using namespace std;

int n;
int a[300][300];
int mark[300][300];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};


bool isbound(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<n)return true;
	return false;
}

void dfs(int x,int y){
	mark[x][y]=1;
	int node=a[x][y];
	int i,j,k;
	for(i=0;i<4;i++){
		int curx=x+dx[i];
		int cury=y+dy[i];
		if(isbound(curx,cury)&&a[curx][cury]==node&&mark[curx][cury]==0){
			dfs(curx,cury);
		}
	}
}

bool check(int p){
	int i,j,k;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(a[i][j]==p&&mark[i][j]==0)return false;
		}
	}
	return true;
}



void main(){
//	ifstream cin("data.txt");
	while(1){
		cin>>n;
		int i,j,k;
		if(n==0)break;
		memset(a,0,sizeof(a));
		memset(mark,0,sizeof(mark));

		for(i=0;i<n-1;i++){
			for(j=0;j<n;j++){
				int x,y;
				cin>>x>>y;
				a[x-1][y-1]=i+1;
			}
		}
		int cur=0;
		bool test=true;
		for(i=0;i<n&&test;i++){
			for(j=0;j<n&&test;j++){
				if(mark[i][j]==0&&a[i][j]==cur){
					dfs(i,j);
					if(check(cur)){
						cur++;
					}else{
						test=false;
					}
				}
			}
		}
		if(test)cout<<"good"<<endl;
		else cout<<"wrong"<<endl;


	}
}

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