Buongiorno a tutti!
Avrei bisogno di una mano per rendere il mio programma per “Tris in solitaria 2” più veloce. Attualmente mi garantisce 80 punti su 100 (va fuori tempo solo nel testcase 48; l’ho testato e sul mio PC impiega ~2.40 sec)
Qualche suggerimento?
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
int board[14][14] = {0}; // Griglia per salvare le croci già piazzate
// (le dimensioni sono 2 in più del massimo
// in modo da poter chiamare 'safe' senza
// errori)
int mx=0, // Massimo di croci piazzate
N, M, // Dimensioni della griglia
prepl=0; // 0 se la griglia non contiene x all'inizio
// del programma, 1 altrimenti
int safe(int r, int c) { // Controlla se piazzare una croce in posizione
//(r, c) genera un tris
int nr = r+2, nc = c+2;
if (board[nr][nc-1]+board[nr][nc-2] == 2) {
return 0;
}
if (board[nr-1][nc-1]+board[nr-2][nc-2] == 2) {
return 0;
}
if (board[nr-1][nc]+board[nr-2][nc] == 2) {
return 0;
}
if (board[nr-1][nc+1]+board[nr-2][nc+2] == 2) {
return 0;
}
if (!prepl) return 1; // Se all'inizio non c'erano croci non
// serve continuare
if (board[nr][nc+1]+board[nr][nc+2] == 2) {
return 0;
}
if (board[nr+1][nc+1]+board[nr+2][nc+2] == 2) {
return 0;
}
if (board[nr+1][nc]+board[nr+2][nc] == 2) {
return 0;
}
if (board[nr+1][nc-1]+board[nr+2][nc-2] == 2) {
return 0;
}
if (board[nr][nc-1]+board[nr][nc+1] == 2) {
return 0;
}
if (board[nr-1][nc-1]+board[nr+1][nc+1] == 2) {
return 0;
}
if (board[nr-1][nc]+board[nr+1][nc] == 2) {
return 0;
}
if (board[nr-1][nc+1]+board[nr+1][nc-1] == 2) {
return 0;
}
return 1;
}
void gioca(int i, int r, int c) { // Funzione ricorsiva
// i -> Croci piazzate in questa iterazione
// (r, c) -> Posizione della cella corrente
if (r==N || N*M-M*r-c <= mx-i) { // Se le celle sono finite o è impossibile
// superare il massimo corrente, interrompi questa
// iterazione
return;
}
int nr=r, nc=c; // Calcola la posizione della prossima cella
if (c==M-1) {
nc = 0;
nr++;
} else {
nc++;
}
gioca(i, nr, nc); // Prova a non mettere una croce qui
if (safe(r, c) && !board[r+2][c+2]) { // Se mettere una croce non genera tris
// (e non c'è già una croce qui)
mx = (mx>i+1)? mx:i+1; // Aggiorna il massimo
board[r+2][c+2] = 1; // Aggiungi un croce in 'board'
gioca(i+1, nr, nc); // Prova a mettere una croce qui
board[r+2][c+2] = 0; // Togli la croce per future iterazioni
}
}
int main() {
stdin = fopen("input.txt", "r");
assert(2 == scanf("%d %d", &N, &M));
int** G = (int**) malloc(N * sizeof(int*));
for(int i = 0; i < N; i++)
G[i] = (int*) malloc(M * sizeof(int));
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
assert(1 == scanf("%d", &G[i][j]));
// Trasferisci tutte le croci da 'G' a 'board'
for (int r=0; r<N; r++) {
for (int c=0; c<M; c++) {
board[r+2][c+2] = G[r][c];
if (G[r][c])
prepl = 1;
}
}
gioca(0, 0, 0);
printf("%d\n", mx);
}