ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1164. Fillword

Is there any trick in test #10
Posted by akademi 12 Mar 2005 15:14
I know I can calculate the anwser directly,but I used DFS algorithm at first.I think it can solve this problem too,but I got WA on test #10,who can tell me WHY? thx.

My code:

/* ural1164 */

#include<iostream>
#include<string.h>

using namespace std;

const way[4][2]={{1,0},{0,-1},{-1,0},{0,1}};

int m,n,p;
char map[15][15];
bool check[15][15];
bool flag,fflag;
char word[150][300];

void init()
{
    int i,j;
    cin>>n>>m>>p;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) cin>>map[i][j];
    for(i=1;i<=p;i++) cin>>word[i];
    fflag=false;
}

void find(int x,int y,int d,int l)
{
    int i,xx,yy;
    if(flag) return;
    check[x][y]=true;
    if(l==strlen(word[d])+1)
    {
        flag=true;
        return;
    }
    for(i=0;i<=3;i++)
    {
        xx=x+way[i][0];
        yy=y+way[i][1];
        if(map[xx][yy]==word[d][l-1] && !check[xx][yy])
            find(xx,yy,d,l+1);
    }
    if(flag) return;
    check[x][y]=false;
    return;
}


void out()
{
    int i,j,l;
    char w;
    char ans[300],*p;
    p=ans;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(!check[i][j])
                *(p++)=map[i][j];
    *p='\0';
    l=strlen(ans);
    for(i=l-1;i>=0;i--)
        for(j=0;j<=i-1;j++)
            if(ans[j]>ans[j+1])
            {
                w=ans[j];
                ans[j]=ans[j+1];
                ans[j+1]=w;
            }
    cout<<ans<<endl;
}


void search(int x)
{
    bool check1[15][15];
    int i,j;
    if(x==p+1)
    {
        out();
        fflag=true;
    }
    if(fflag) return;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(map[i][j]==word[x][0] && !check[i][j])
            {
                memmove(check1,check,sizeof(check));
                flag=false;
                find(i,j,x,2);
                if(flag) search(x+1);
                memmove(check,check1,sizeof(check1));
            }
}



void work()
{
    memset(check,false,sizeof(check));
    search(1);
}



int main()
{
    init();
    work();
    return 0;
}
Re: Is there any trick in test #10
Posted by Burunduk1 12 Mar 2005 21:07
I think there is no trick in this test.
There is more simple solution (only 15 strings code)...
Try to find it!