Testcase 16 errato OIS_Glados


#1

Salve, sto provando a risolvere ois_glados, ma non capisco perché continuo a sbagliare il testacase 16. Il mio programma, che allego sotto, cerca ogni volta la direzione giusta girando progressivamente in senso antiorario, a meno che la casella immediatamente a destra non sia bianca, nel qual caso scelgo direttamente quella direzione. Facendo un paio di prove, ho capito che il testcase ha come risultato “stuck”, mentre il mio programma, da quanto ho capito, ritorna “cycling”. Pensavo appunto che il problema fosse il modo in cui appunto controllavo che un percorso fosse ciclico, ossia ripetendo il ciclo un po’ di volte per avere la certezza. Tuttavia anche ripetendolo più di 100 volte il testcase 16 continua a essere sbagliato. Grazie per l’aiuto.

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

ifstream in("input.txt");
ofstream out("output.txt");

int h,w,cox,coy;
bool flag=0;
int ucx=-1;
int ucy=-1;
int hk=0;

char tab[200][200];
bool e[200][200];
string r;
int cx(int x, char o){
	if(o=='n')return x-1;
	if(o=='s')return x+1;
	return x;
}
int cy(int y, char o){
	if(o=='o')return y-1;
	if(o=='e')return y+1;
	return y;
}
int calcx(int x, char o){
	if(o=='o')return x-1;
	if(o=='e')return x+1;
	return x;
}
int calcy(int y, char o){
	if(o=='s')return y-1;
	if(o=='n')return y+1;
	return y;
}
char co(char o){
	if(o=='n')return 'o';
	if(o=='o')return 's';
	if(o=='s')return 'e';
	if(o=='e')return 'n';
}
char coq(char o){
	if(o=='n')return 'e';
	if(o=='o')return 'n';
	if(o=='s')return 'o';
	if(o=='e')return 's';
}

string rec(int x,int y,int o){
	if(tab[x][y]=='O')return "free";
	if(tab[x][y]=='@')return "stuck";
	if(e[x][y]&&x==ucx&&y==ucy){
	    
	    if(hk>100)
	    return "cycling";
	    hk++;
	}
	if(e[x][y]){
		if(!flag){
		    flag=1;
			ucx=x;
			ucy=y;
		}
	}
	
	
	e[x][y]=1;
	if(tab[calcx(x,o)][calcy(y,o)]=='.'){
		
		return rec(cx(x,coq(o)),cy(y,coq(o)),coq(o));
	}
	while(tab[cx(x,o)][cy(y,o)]=='#'){
		o=co(o);	
	}
	return rec(cx(x,o),cy(y,o),o);
	
}
int main(){
	in>>h>>w>>cox>>coy;
	for(int i=0;i<h;i++){
		for(int y=0;y<w;y++){
			in>>tab[i][y];
			e[i][y]=0;
		}
	}
	out<<rec(cox,coy,'n');
}

#2

Ecco un semplice input in cui il tuo programma sbaglia:

5 5 3 1
#####
#...#
#.@.#
#.#.#
#...#
#####

#3

Forse allora non ho capito bene il testo. Se non c’è nessuna parete sulla destra dove dovrebbe dirigersi?


#4

Effettivamente hai ragione, quell’input non rispettava le assunzioni del testo :joy:
Adesso ho corretto, comunque la logica per cui sbaglia è la stessa.


#5

Cavolo grazie mille, ho capito