OJ Board

Code: Select all

###...
###...
##..##
...###
..####
..####

Code: Select all

#include<iostream>

using namespace std;

const int mmax=5;
int mapmax;
char map[mmax+1][mmax+1];
int dotmax;

void track(int y,int x,char ch){
	int i;
	//y->i
	for(i=y-1;i>=0;i--){
		if(map[i][x]=='X' || map[i][x]=='O')
			break;
		map[i][x]=ch;
	}
	for(i=y+1;i<=mapmax;i++){
		if(map[i][x]=='X' || map[i][x]=='O')
			break;
		map[i][x]=ch;
	}
	//x->i
	for(i=x-1;i>=0;i--){
		if(map[y][i]=='X' || map[y][i]=='O')
			break;
		map[y][i]=ch;
	}
	for(i=x+1;i<=mapmax;i++){
		if(map[y][i]=='X' || map[y][i]=='O')
			break;
		map[y][i]=ch;
	}
}

void log(int dots){
	if(dots>dotmax)
		dotmax=dots;
}

void dfs(int y,int x,int dots){
	log(dots);
	for(;y<=mapmax;y++){
		for(;x<=mapmax;x++){
			if(map[y][x]=='.'){
				map[y][x]='O';
				track(y,x,'-');
				dfs(y,x,dots+1);
				map[y][x]='.';
				track(y,x,'.');
			}
		}
		x=0;
	}
}

int main(){
	int x,y;
	while(cin>>mapmax){
		//last case
		if(mapmax==0)
			break;
		//len->limit
		mapmax--;
		//default
		for(y=0;y<=mmax;y++){
			for(x=0;x<=mmax;x++){
				map[y][x]='.';
			}
		}
		dotmax=0;
		//input
		for(y=0;y<=mapmax;y++){
			cin>>map[y];
		}
		dfs(0,0,0);
		cout<<dotmax<<endl;
	}
	return 0;
}

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX 4
char tab[MAX][MAX];
void leerTab(char tab[MAX][MAX], int tam){
    int i,j;
    for(i=0;i<tam;i++)
        for(j=0;j<tam;j++){
            int car;
            scanf(" %c",&tab[i][j]);
       }
            
}
int max(int value1, int value2){
    if (value1>value2) return value1;
    return value2;
}
void buscaPo(int fil, int col,int tam,int* sx, int *sy){
   *sx = fil+1;
   *sy = col;
   if (*sx == tam){
       *sx = 0;
       *sy = col+1;
   }
}
int isSafe(int fil, int col,char tab[MAX][MAX], int tam){
    int i;
    if (tab[fil][col] == 'X' || tab[fil][col] == 'T')
        return 0;
    for(i=col-1;i>=0;i--){
        if (tab[fil][i] == 'X') break;
        if (tab[fil][i] == 'T') return 0;
    }
    for(i=fil-1;i>=0;i--){
       if (tab[i][col] == 'X') break;
       if (tab[i][col] == 'T') return 0;
    }
    return 1;    
}
void llena(int fil,int col,int tam, char tab[MAX][MAX],int *ntorres,int *maxi){
    if (col == tam){
        *maxi = max(*ntorres,*maxi);
        return;
    }
    int sig_x,sig_y;
    
    buscaPo(fil,col,tam,&sig_x,&sig_y);
    if ( isSafe(fil,col,tab,tam) ){
        tab[fil][col] = 'T';
        (*ntorres)++;
        llena(sig_x,sig_y,tam,tab,ntorres,maxi);
        tab[fil][col] = '.';
        (*ntorres)--;
    }
    llena(sig_x,sig_y,tam,tab,ntorres,maxi);
}
int main(int argc, char** argv) {
    int tam;
   while ( scanf("%d",&tam) != EOF ){
        leerTab(tab,tam);
        int torres = 0, mtorres = 0;
        llena(0,0,tam,tab,&torres,&mtorres);
        printf("%d\n",mtorres);
    }
    return 0;
}