this is the link to problem: http://acmicpc-live-archive.uva.es/nuevoportal/
an anyone help me to find where I made error in solving this problem....
In my thought, it's a simple problem, just need to loop from top to down, left to right to find the empty cells.
When I reach an empty cell, if this cell can be filled, it must be filled by the top cell of a "plus" title. I assign this "plus" title by using the smallest character that doesn't break any constraint with its neighbor.
I continue going and filling cells until the end of wall, If I can fill all the empty cells, the answer is possible, otherwise, the answer is impossible.
this is my code:
int n;
vector<string> a;
bool res;
int dx[] = {1, 0, 1, 2, 1};
int dy[] = {-1, 0, 0, 0, 1};
int ax[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int ay[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool isIn(int x, int y){
return (0<=x && x<n && 0<=y && y<n);
}
bool fill(int x, int y){
bool check[4];
For(i, 0, 3) check[i] = true;
For(i, 0, 4){
int xx = x + dx[i];
int yy = y + dy[i];
if(!isIn(xx, yy) || a[xx][yy] != '.') return false;
For(j, 0, 7){
int x1 = xx + ax[j];
int y1 = yy + ay[j];
if(isIn(x1, y1) && a[x1][y1] != '.') check[ a[x1][y1] - 'A' ] = false;
}
}
char color = 'Z';
For(i, 1, 3) if(check[i]){
color = i + 'A';
break;
}
if(color == 'Z') return false;
For(i, 0, 4){
int xx = x + dx[i];
int yy = y + dy[i];
a[xx][yy] = color;
}
return true;
}//end;
void solve(){
res = true;
For(i, 0, n-1) For(j, 0, n-1) if(a[i][j] == '.'){
if(!fill(i, j)){
res = false;
return;
}
}
}
int main(){
freopen("p4997_in.txt", "rt", stdin); freopen ("output.txt","w",stdout);
int sotest;
cin >> sotest;
For(run, 1, sotest){ cout << "Case " << run << ":";
cin >> n;
a.clear();
string str;
For(i, 0, n-1){
cin >> str; a.pb(str);
}
solve();
if(!res) cout << " Not Possible!" << endl;
else{
cout << endl;
For(i, 0, n-1) cout << a[i] << endl;
}
}//end for;
return 0;
}
many thanks in advance!
