Задача овци олимпијада 2009

This message was edited 1 time. Last update was at 24/04/2012 23:15:38

Дали можи да ми помогните со задачава, вади рантајм ерор на повеќето случаи...
еве го кодот, а супер би ми дошол и некој тест пример за да видам кај имам грешка, поминува само на 2 примери

#include <iostream>

using namespace std;

int prazni = 0;
int ovci = 0, volci = 0;
char matrica[255][255];

void find(int x,int y)
{
	if((matrica[x+1][y] == '.') || (matrica[x+1][y] == 'o') || (matrica[x+1][y] =='v'))
	{
		if(matrica[x+1][y] == 'o')
		{
			ovci++;
		}
		if(matrica[x+1][y] == 'v')
		{
			volci++;
		}
		matrica[x+1][y] = '!';
		prazni--;
		find(x+1,y);
	}
	if((matrica[x-1][y] == '.') || (matrica[x-1][y] == 'o') || (matrica[x-1][y] =='v'))
	{
		if(matrica[x-1][y] == 'o')
		{
			ovci++;
		}
		if(matrica[x-1][y] == 'v')
		{
			volci++;
		}
		matrica[x-1][y] = '!';
		prazni--;
		find(x-1,y);
	}
	if((matrica[x][y+1] == '.') || (matrica[x][y+1] == 'o') || (matrica[x][y+1] =='v'))
	{
		if(matrica[x][y+1] == 'o')
		{
			ovci++;
		}
		if(matrica[x][y+1] == 'v')
		{
			volci++;
		}
		matrica[x][y+1] = '!';
		prazni--;
		find(x,y+1);
	}
	if((matrica[x][y-1] == '.') || (matrica[x][y-1] == 'o') || (matrica[x][y-1] =='v'))
	{
		if(matrica[x][y-1] == 'o')
		{
			ovci++;
		}
		if(matrica[x][y-1] == 'v')
		{
			volci++;
		}
		matrica[x][y-1] = '!';
		prazni--;
		find(x,y-1);
	}
	if((matrica[x][y] == '.') || (matrica[x][y] == 'o') || (matrica[x][y] =='v'))
	{
		matrica[x][y] = '!';
		prazni--;
	}
}
int main()
{
	int goleminaA,goleminaB;
	int i,j,k,tmp;
	int brojOvci,brojVolci;
	brojOvci = 0;
	brojVolci = 0;
	cin >> goleminaA >> goleminaB;

for(i = 0; i < goleminaA; i++)
	{
		for(j = 0; j < goleminaB; j++)
		{
			cin >> matrica[i][j];
			if(matrica[i][j] == '.'||matrica[i][j] == 'o'||matrica[i][j] == 'v')
				prazni++;
		}
	}

for(i = 0; i < goleminaA; i++)
	{
		for(j = 0; j < goleminaB; j++)
		{
			if(matrica[i][j] == '.')
			{
				find(i,j);
				if(volci >= ovci)
				{
					ovci = 0;
					brojVolci += volci;
					volci = 0;
				}
				else
				{
					brojOvci += ovci;
					ovci = 0;
					volci = 0;
				}
			}
		}
	}

cout<<brojOvci<<' '<<brojVolci;

return 0;
}

матрицата беше помала, ама пак на пола не оди...

Ја провери задачата во дебагер?

Прво, не печатиш нов ред после одговорот, ама тоа не предизвикува runtime error.

Второ, во find никаде не проверуваш дали излегуваш надвор од границите на матрицата, и тоа 99% е причината за runtime error-от што го добиваш.

ја решив, и да, то беше еден од проблемите :Д

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int R, S;
bool WithinRange(int x, int y)
{
	if((x>=0 && x<R) && (y>=0 && y<S))
		return true;
	return false;
}
int main()
{
	cin>>R>>S;
	char MAT[R][S];
	vector<pair<int, int> > Ovci;
	vector<pair<int, int> > Volk;
	for(int i=0;i<R;i++)
	{
		for(int j=0;j<S;j++)
		{
			cin>>MAT[i][j];
			if(MAT[i][j]=='o')
			Ovci.push_back(make_pair(i,j));
			if(MAT[i][j]=='v')
			Volk.push_back(make_pair(i,j));
		}
	}
	bool VIS[R][S];
	memset(VIS,false,sizeof(VIS));
	int delta_x[]={1,0,-1,0};
	int delta_y[]={0,1,0,-1};
	queue<pair<int, int> > q;
	vector<int> survive_Ovci;
	vector<int> survive_Volk;
	int pom_Ovci=0;
	int pom_Volk=0;
	for(int i=0;i<Ovci.size();i++)
	{
		pair<int,int> at1=Ovci[i];
		if(VIS[at1.first][at1.second]==false)
		{
			q.push(at1);
			while(!q.empty())
			{
				pair<int, int> at=q.front();
				q.pop();
				for(int dir=0;dir<4;dir++)
				{
					int x=at.first, y=at.second;
					int next_x=x+delta_x[dir], next_y=y+delta_y[dir];
					if( WithinRange(next_x, next_y)==true && VIS[next_x][next_y]==false && MAT[next_x][next_y]!='#' )
					{
						q.push(make_pair(next_x,next_y));
						VIS[next_x][next_y]=true;
						if(MAT[next_x][next_y]=='o')
						pom_Ovci++;
						if(MAT[next_x][next_y]=='v')
						pom_Volk++;
					}	
				}
			}
		}
		if(pom_Ovci>pom_Volk)
		{
		survive_Ovci.push_back(pom_Ovci);
		pom_Ovci=0;
		survive_Volk.push_back(0);
		pom_Volk=0;
		}
		else
		{
		survive_Volk.push_back(pom_Volk);
		pom_Ovci=0;
		survive_Ovci.push_back(0);
		pom_Volk=0;
		}
		
	}
	for(int i=0;i<Volk.size();i++)
	{
		pair<int, int> at1=Volk[i];
		if(VIS[at1.first][at1.second]==false)
		{
			q.push(at1);
			while(!q.empty())
			{
				pair<int,int> at=q.front();
				q.pop();
					for(int dir=0;dir<4;dir++)
				{
					int x=at.first, y=at.second;
					int next_x=x+delta_x[dir], next_y=y+delta_y[dir];
					if( WithinRange(next_x, next_y)==true && VIS[next_x][next_y]==false && MAT[next_x][next_y]!='#' )
					{
						q.push(make_pair(next_x,next_y));
						VIS[next_x][next_y]=true;
						if(MAT[next_x][next_y]=='o')
						pom_Ovci++;
						if(MAT[next_x][next_y]=='v')
						pom_Volk++;
					}	
				}
			}
		}
		if(pom_Ovci>pom_Volk)
		{
		survive_Ovci.push_back(pom_Ovci);
		pom_Ovci=0;
		survive_Volk.push_back(0);
		pom_Volk=0;
		}
		else
		{
		survive_Volk.push_back(pom_Volk);
		pom_Ovci=0;
		survive_Ovci.push_back(0);
		pom_Volk=0;
		}
		
	}
	int survived_O=0;
	int survived_V=0;
	int bigger;
	int diff;
	if(survive_Ovci.size()>survive_Volk.size())
	{
	bigger=survive_Ovci.size();
	diff=survive_Ovci.size()-survive_Volk.size();
	}
	else
	{
	bigger=survive_Volk.size();
	diff=bigger-survive_Ovci.size();
	}
	for(int i=0;i<bigger;i++)
	{
		survived_O+=survive_Ovci[i];
		survived_V+=survive_Volk[i];
	}
	cout<<survived_O<<" "<<survived_V<<endl;
	return 0;
}

Ако може малку помош ми работи на 7 тест случаеви од можни десет, незнам каде му е грешката , помош!!!

MODDI wrote:Ако може малку помош ми работи на 7 тест случаеви од можни десет, незнам каде му е грешката , помош!!!

Кај првата овца/волк, кога почнуваш со BFS-то.

Додади кај првото BFS (одма после q.push(at1)) само

и кај второто BFS (одма после q.push(at1)) само