Quasi palindromi: scambio righe

Aiuto
1

Come mai ottengo solo 11.11 punti su 100?

Quasi per tutti i task ottengo Execution timed out, in due task è errato l’output.

#include <iostream>
#include <fstream>
using namespace std;
const int MAX=8;
char mat[MAX][MAX],lett[MAX];
char s[MAX];
bool palin(char s[],int m);
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int m,n;
	cin>>m>>n;
	for(int i=0;i<m;i++)
	{
		cin>>lett;
		for(int j=0;j<n;j++)
			mat[i][j]=lett[j];
	}
	
	bool contr=false;
	int cont=m-1;
	while(contr==false)
	{
		contr=true;
		for(int j=0;j<n and contr==true;j++)
		{
			for(int i=0;i<m;i++)
			{
				s[i]=mat[i][j];
			}
			if(palin(s,m)==true) contr=true;
			else contr=false;
		}
		if(contr==true)
		{
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<n;j++)
					cout<<mat[i][j];
				cout<<endl;
			}
		}
		else
		{
			for(int j=0;j<n;j++)
			{
				int temp=mat[cont][j];
				mat[cont][j]=mat[cont-1][j];
				mat[cont-1][j]=temp;
			}
		}
		if(cont==1) cont=m-1;
		else
		cont--;
	}
	
}
bool palin(char s[],int m)
{
	for(int i=0,j=m-1;i<m/2;i++ and j--)
	{
		if(s[i]!=s[j] and s[i]!='0' and s[j]!='0')
		{ 
			return false;
		}
	}
	return true;
}
2 Mi Piace
2

Se potessi spiegare brevemente cosa fa il tuo codice sarebbe più semplice aiutarti, in ogni caso dando un’occhiata veloce mi pare che tu non stai provando tutte le permutazioni delle stringhe.

2 Mi Piace
3

Il codice legge la matrice
Per ogni riga salva tutti i numeri della stessa colonna in una stringa
Controlla se la stringa è un numero palindromo
Se tutte le stringhe sono numeri palindromi stampa la matrice
Altrimenti controllo una nuova configurazione: porto l’ultima riga sempre più in alto e, quando diventa la prima, ricomincio con l’ultima (in questo modo dovrei provare tutte le permutazioni)

2 Mi Piace
4

In realtà questo è vero solo se hai N<=3 elementi da permutare, già con N=4 ti accorgi che in realtà provi solo N*(N-1) configurazioni:
ABCD, ABDC, ADBC
DABC, DACB, DCAB
CDAB, CDBA, CBDA
BCDA, BCAD, BACD
A questo punto la prossima configurazione generata dal tuo algoritmo sarà ABCD che è stata già visitata, quindi se il tuo programma non trova un rettangolo palindromo tra una delle N*(N-1) configurazioni generate vai a finire in un loop (il che spiega i TLE).

2 Mi Piace
5

:face_with_raised_eyebrow:Hai ragione
Ho trovato questo interessante programma per le permutazioni di una stringa ma non riesco ad adattarlo al problema. Qualche idea?

#include <stdio.h>
#include <string.h>

//prototipi di funzione
void Swap(char* string,int i,int j);
void Permutations(char *string,int i ,int n);


void main()
{
char s[256];//poi per lungezze maggiori ti arrangi tu ma tanto il tempo di esecuzione 
//cresce col fattoriale e non conviene esagerare con la lungezza....
printf("Dammi la stringa (max 255 caratteri):");
scanf("%s",s);
Permutations(s,0,(int)strlen(s)-1);
}


//Genera ricorsivamente le permutazioni
void Permutations(char *string,int i ,int n)
{
int j;
if(i==n)
{
for(j=0;j<=n;j++)
printf("%c",string[j]);
printf("\n");
}
else
{
for( j = i ; j<=n ; j++ )
{
Swap(string,i,j);
Permutations(string,i+1,n);
Swap(string,i,j);
}
}
}

//Effettua un semplice scambio di posizione
void Swap(char* string,int i,int j)
{
int temp;
temp = string[i];
string[i] = string[j];
string[j] = temp;
}
2 Mi Piace
6

Secondo me il modo più rapido per permutare gli elementi di un array è salvarsi degli oggetti di tipo string in un array e poi utilizzare la funzione “next_permutation” della libreria algorithm.
Ecco qui un esempio: https://pastebin.com/PDTf9K8W

2 Mi Piace
7

Ho inserito la funzione next_permutation. Sembra molto utile ma il risultato è sempre lo stesso. Dove sbaglio?

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int MAX=8;
char mat[MAX][MAX],lett[MAX];
char s[MAX];
int perm[MAX];
bool palin(char s[],int m);
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int m,n;
	cin>>m>>n;
	for(int i=0;i<m;i++)
	{
		cin>>lett;
		for(int j=0;j<n;j++)
			mat[i][j]=lett[j];
		perm[i]=i;
	}
	
	bool contr=false;
	int cont=m-1;
	do
	{
		contr=true;
		for(int j=0;j<n and contr==true;j++)
		{
			for(int i=0;i<m;i++)
			{
				s[i]=mat[i][j];
			}
			if(palin(s,m)==true) contr=true;
			else contr=false;
		}
		if(contr==true)
		{
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<n;j++)
					cout<<mat[i][j];
				cout<<endl;
			}
		}
		else
		{
			next_permutation(perm, perm+m);
		}
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				char temp[MAX];
				temp[j]=mat[perm[i]][j];
				mat[perm[i]][j]=mat[i][j];
				mat[i][j]=temp[j];
			}
		}
	}while(contr==false);
	
}
bool palin(char s[],int m)
{
	for(int i=0,j=m-1;i<m/2;i++ and j--)
	{
		if(s[i]!=s[j] and s[i]!='0' and s[j]!='0')
		{ 
			return false;
		}
	}
	return true;
}
2 Mi Piace
8

Ma… Perché questa cosa?

Tipo se i==0 non eseguirà l’istruzione j-- o sbaglio?

Forse sarebbe meglio scrivere i++, j-- ma non so cosa fa quel codice quindi potrei sbagliarmi.

2 Mi Piace
9

Hai ragione è proprio quello il problema. Ecco il codice che mi permette di ottenere 100/100

  #include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int MAX=8;
char mat[MAX][MAX],lett[MAX];
char s[MAX];
int perm[MAX];
bool palin(char s[],int m);
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int m,n;
	cin>>m>>n;
	for(int i=0;i<m;i++)
	{
		cin>>lett;
		for(int j=0;j<n;j++)
			mat[i][j]=lett[j];
		perm[i]=i;
	}
	
	bool contr=false;
	int cont=m-1;
	do
	{
		contr=true;
		for(int j=0;j<n and contr==true;j++)
		{
			for(int i=0;i<m;i++)
			{
				s[i]=mat[i][j];
			}
			if(palin(s,m)==true) contr=true;
			else contr=false;
		}
		if(contr==true)
		{
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<n;j++)
					cout<<mat[i][j];
				cout<<endl;
			}
		}
		else
		{
			next_permutation(perm, perm+m);
		}
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				char temp[MAX];
				temp[j]=mat[perm[i]][j];
				mat[perm[i]][j]=mat[i][j];
				mat[i][j]=temp[j];
			}
		}
	}while(contr==false);
	
}
2 Mi Piace