uva639 - Don't Get Rooked

이 문제 에 대해 20ms 를 달 리 는 코드 를 만 들 기 시 작 했 고 한 시간 동안 최적화 한 후에 12ms 를 달 렸 습 니 다.
생각 이 어렵 지 않 은 것 은 문 제 를 한 걸음 한 걸음 나 누 는 것 이다.
한 걸음 한 걸음 씩 재 귀 하면 된다.먼저 20ms 코드 를 붙 여 주세요 /
코드 는 다음 과 같 습 니 다:
#include <cstdio>
char f[5][5];
int  n, max;
int is_caninset(int c, int l)
{
    if(f[c][l]=='X'||f[c][l]=='/'||f[c][l]=='o')return 0;
    for(int i = l+1; i < n; i++)
    if(f[c][i]=='X') break;
    else if(f[c][i]=='/') return 0;
    for(int i = l-1; i >= 0; i--)
    if(f[c][i]=='X') break;
    else if(f[c][i]=='/') return 0;
    for(int i = c+1; i < n; i++)
    if(f[i][l]=='X') break;
    else if(f[i][l]=='/') return 0;
    for(int i = c-1; i >= 0; i--)
    if(f[i][l]=='X') break;
    else if(f[i][l]=='/') return 0;
    return 1;
}
void printf_permutation(int c, int l, int num)
{
    int t = 0;
    f[c][l] = '/';
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    if(is_caninset(i,j)){t++; printf_permutation(i,j,num+1);}
    if(!t)  max = max<num?num:max;
    f[c][l] = '.';
}
int main ()
{
    while(scanf("%d",&n)&&n)
    {
        getchar();
        for(int i = 0; i < n; i++, getchar())
        for(int j = 0; j < n; j++)
        scanf("%c",&f[i][j]);
        max = 0;
        for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        if(is_caninset(i,j)) printf_permutation(i,j,1);
        printf("%d
",max); } return 0; }
12ms 코드 를 다시 붙 여 주세요.
#include <cstdio>
char f[5][5];
int  n;
int is_caninset(int c, int l)
{
    if(f[c][l]=='X'||f[c][l]=='/'||f[c][l]=='o')return 0;
    for(int i = l-1; i >= 0; i--)
    if(f[c][i]=='X') break;
    else if(f[c][i]=='/') return 0;
    for(int i = c-1; i >= 0; i--)
    if(f[i][l]=='X') break;
    else if(f[i][l]=='/') return 0;
    return 1;
}
int printf_permutation(int c, int l)
{
    int t = 0, max = 0;
    f[c][l] = '/';
    for(int i = c; i < n; i++)
    for(int j = (i==c?l+1:0); j < n; j++)
    if(is_caninset(i,j)){t = printf_permutation(i,j)+1; max = max<t?t:max;}
    f[c][l] = '.';
    return max;
}
int main ()
{
    int max, t;
    while(scanf("%d",&n)&&n)
    {
        getchar();
        for(int i = 0; i < n; i++, getchar())
        for(int j = 0; j < n; j++)
        scanf("%c",&f[i][j]);
        max = 0;
        for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        if(is_caninset(i,j)) {t = printf_permutation(i,j)+1; max = max < t? t: max;}
        printf("%d
",max); } return 0; }

좋은 웹페이지 즐겨찾기