Page 1 of 1
10563 - Least Squares
Posted: Thu Oct 09, 2003 12:25 am
by 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]
Posted: Thu Oct 09, 2003 5:02 am
by 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.
Posted: Thu Oct 09, 2003 12:12 pm
by 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]
Posted: Fri Oct 10, 2003 5:54 pm
by 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]
10563
Posted: Fri Oct 17, 2003 4:46 am
by 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.
10563 Least Squares
Posted: Fri Oct 17, 2003 7:02 am
by horape
Last one is bad. It should be:
Posted: Tue Mar 16, 2004 6:44 pm
by Larry
Why?
Posted: Tue Mar 16, 2004 9:24 pm
by 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.
Posted: Tue Mar 16, 2004 11:35 pm
by Larry
But doesn't JP's solution uses only 8 squares, while horape's is 13?
Posted: Tue Mar 16, 2004 11:45 pm
by Adrian Kuegel
Instead, your much simpler task is merely to cover it with squares. That's it.
Did you read that
Posted: Wed Mar 17, 2004 12:05 am
by Larry
Ah.. I see, I misinterpreted the problem all this time.. =) Now it's so much easier.. thanks!
Posted: Tue Sep 12, 2006 5:35 am
by 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...
Posted: Wed Sep 27, 2006 5:08 pm
by rio
this will may be your critical test case, minskcity.
4 5
???..
???.?
?????
?????
0 0
try it.
Posted: Wed Sep 27, 2006 5:48 pm
by minskcity
rio wrote:this will may be your critical test case, minskcity.
Thank, I've already got AC
.
Posted: Fri Mar 28, 2008 5:38 pm
by Robert Gerbicz
minskcity wrote:rio wrote: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:
Very tricky problem.