10563 - Least Squares

[hj]

Hi!
I can't find what's wrong with my sourcecode. I keep getting WA. Could sombody post some tests ??. Here is my source. I think this problem is rather easy o i misunderstood samething...

[cpp]
#include <iostream.h>

#define min(a,b)(a<b ? a : b)
#define MAX 110

char tab[MAX][MAX];
char c[255];


int main(){
int m,n;
int f=0;
cin >> m >>n;
while (m && n){
if (f) cout << endl; f=1;
for (int i=0;i<m;++i) cin >> tab;
//for(int i=0;i<m;++i) cout << tab<<endl;

for (int i=0;i<m;++i)
for (int j=0;j<n;++j)
if (tab[j]=='?')
{
int w=i+1,k=j+1;
int dalej=1;
while (w<m && k<n && dalej){
int a=i;
while (a<=w && tab[a][k]=='?') ++a;
if (a<=w) dalej=0;
if (dalej){
a=j;
while(a<=k && tab[w][a]=='?') ++a;
if(a<=k) dalej=0;
else { ++w; ++k;}
}
}
--w; --k;
// cout << "i="<<i<<" j="<<j<<" w="<<w<<" k="<<k<<endl;
for(int u='A';u<='Z';++u) c=0;
if (j>=1) for (int u=i; u<=w; ++u) if (tab[j-1]!='.' && tab[j-1]!='?') c[tab[j-1]]=1;
if (j<n-1) for (int u=i; u<=w; ++u) if (tab[j+1]!='.' && tab[j+1]!='?') c[tab[j+1]]=1;
if (i>=1) for (int u=j; u<=k; ++u) if (tab[i-1]!='.' && tab[i-1]!='?' ) c[tab[i-1]]=1;
if (i<m-1) for (int u=j; u<=k; ++u) if (tab[i+1][u]!='.' && tab[i+1][u]!='?') c[tab[i+1][u]]=1;
int cc='A';
while(c[cc]) ++cc;
for (int p=i;p<=w;++p)
for(int q=j;q<=k;++q)
tab[p][q]=(char)(cc);

}
for(int i=0;i<m;++i) {
for(int j=0;j<n;++j) cout << tab[j]; cout<<endl;
}


cin >> m >>n;
}
return 0;
}
[/cpp]

[sharklu2000]

what do you think the right output to follows

Code: Select all

5 6
?.????
.?.???
??????
??????
??????

your output is

Code: Select all

A.ABBB
.A.BBB
BBBBBB
BBBAAC
BBBAAB

it's wrong.

[inkfish]

My algorithm is Greedy
i don't know what is wrong with it
can anyone give me some datas or some hints
thanks
[cpp]


#include <iostream.h>
char board[110][110];

char find(int n,int i,int j)
{
char color='A';
while(1){
if((!i || board[i-1][j]!=color) &&
(!j || board[j-1]!=color) &&
(j==n-1 || board[j+1]!=color))break;
color++;
}
return color;
}

int isok(int m,int n,int i,int j,int len)
{
int k;
if(i+len<m && j+len<n){
for(k=0;k<=len;k++)
if(board[i+k][j+len]!='?' || board[i+len][j+k]!='?') return 0;
return 1;
}else return 0;
}

void search(int m,int n,int i,int j)
{
char c1,c2;
int len,k;

c1=find(n,i,j);
board[j]=c1;
len=0;
while(++len){
if(j+len>=n || board[j+len]!='?') break;
c2=find(n,i,j+len);
if(c2<c1) break;

if(isok(m,n,i,j,len) && (j+len+1>=n || board[j+len+1]!=c1)){
for(k=0;k<=len;k++) board[i+k][j+len]=board[i+len][j+k]=c1;
}else break;
}
}

int main()
{
int m,n,i,j;
int first=1;
while(1){
cin>>m>>n;
if(!n && !m) break;
for(i=0;i<m;i++)
for(j=0;j<n;j++) cin>>board[j];
for(i=0;i<m;i++)
for(j=0;j<n;j++){
if(board[j]=='?') search(m,n,i,j);
}
if(first) first=0; else cout<<endl;
for(i=0;i<m;i++){
for(j=0;j<n;j++) cout<<board[j];
cout<<endl;
}
}
return 0;
}[/cpp]

[inkfish]

Ac now
[cpp]
void search(int m,int n,int i,int j)
{
char c1,c2;
int len,k;

c1=find(n,i,j);
board[j]=c1;
len=0;
while(++len){
if(j+len>=n || board[j+len]!='?') break;
c2=find(n,i,j+len);
if(c2<c1) break;

if(isok(m,n,i,j,len) && (j+len+1>=n || board[j+len+1]!=c1)
&& (!i || board[i-1][j+len]!=c1)){
~~~~~~~~~~~~~~~~~~~~~~add this one
for(k=0;k<=len;k++) board[i+k][j+len]=board[i+len][j+k]=c1;
}else break;
}
}
[/cpp]

[jpfarias]

Plz, give me the output of this input:

Code: Select all

5 5
????.
???.?
?????
?????
????.
5 5
????.
???.?
?????
?????
????.
5 5
.....
.....
.....
.....
.....
5 5
?????
?????
?????
?????
?????
5 5
?????
.???.
.???.
.???.
?????
0 0

My output is:

Code: Select all

AAAB.
AAA.A
AAABB
BBCBB
BBAC.

AAAB.
AAA.A
AAABB
BBCBB
BBAC.

.....
.....
.....
.....
.....

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA

ABBBA
.BBB.
.BBB.
.AAC.
BAABA

What's wrong? I'm getting WA...
I would like other input/output if my output is correct...

JP.

[horape]

Last one is bad. It should be:

Code: Select all

ABAAB
.CAA.
.ABB.
.CBB.
ABACA

[Larry]

Why?

[Adrian Kuegel]

Why? Just look at the 3rd position in row 1 (first 2 characters are equal). In the solution of Horape there is an 'A', in the other output a 'B'. 'A' < 'B', so solution of Horape comes lexicographic first.

[Larry]

But doesn't JP's solution uses only 8 squares, while horape's is 13?

[Adrian Kuegel]

Instead, your much simpler task is merely to cover it with squares. That's it.

Did you read that

[Larry]

Ah.. I see, I misinterpreted the problem all this time.. =) Now it's so much easier.. thanks!

[minskcity]

I'm using the following approach: scan the matrix in row-major order, if '?' is seen determing the smallest letter that can be put there; if that letter is 'A', grow the square as much as posible; if that letter is 'B', grow the square as long as the next '?' cannot be set to 'A'; if that letter is 'C' don't grow the square.

Can anybody tell me why that approach is wrong? I keep getting WA...

Never mind, got it. My approach was wrong. There can be Ds...

[rio]

this will may be your critical test case, minskcity.

4 5
???..
???.?
?????
?????
0 0

try it.

[minskcity]

this will may be your critical test case, minskcity.

Thank, I've already got AC .

[Robert Gerbicz]

this will may be your critical test case, minskcity.

Thank, I've already got AC .

That's very interesting, because that algorithm is still totally wrong, and should be broken for the following test:

Code: Select all

5 5
???..
???.?
?????
?????
.??..
0 0

My AC code prints the following:

Code: Select all

AAA..
AAA.A
AAABB
BCCBB
.CC..

Very tricky problem.