Solution UVA: 639 - Don't Get Rooked

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss639 - Don't Get Rooked	Accepted	C++11	0.000	0.000	1084	8 mins ago

Suggest:

- The first algorithm I came up with was recursion, but I didn't use it because in the context of Iterative (Combination), I thought recursion was unnecessary.

- Next, I thought about a greedy approach to see if there was any optimal placement and how to determine its optimality.

- The answer is quite simple: try placing the rook in a position that minimizes the number of empty squares it occupies.

- Since the previous placement was already optimal, we only need to continue finding the next optimal positions until no more placements are possible.

- The number of times we find an optimal position is also the solution to the problem.

#include<bits/stdc++.h>

using namespace std;

const int N= 4;

int n;

char a[N][N];

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(cin >> n && n){

        int point= 0;

        for(int i=0; i<n; i++) for(int j=0; j<n; j++){

                cin >> a[i][j];

                if (a[i][j]=='.') point++;

            }

       

        int rock= 0;

        while(point > 0){

            rock++;

           

            int min_cnt= 16, u=-1, v=-1;

            for(int i=0; i<n; i++) for(int j=0; j<n; j++)

            if (a[i][j] == '.'){

               

                int cnt= 0;

                for(int jj=j; jj<n; jj++)

                    if (a[i][jj]=='X') break; else cnt++;

                for(int jj=j; jj>=0; jj--)

                    if (a[i][jj]=='X') break; else cnt++;

                for(int ii=i; ii<n; ii++)

                    if (a[ii][j]=='X') break; else cnt++;

                for(int ii=i; ii>=0; ii--)

                    if (a[ii][j]=='X') break; else cnt++;

               

                if (cnt-3 < min_cnt){

                    min_cnt= cnt-3; u= i; v= j;

                }

            }

           

            if (u!=-1 && v!=-1){

           

                for(int jj=v; jj<n; jj++)

                    if (a[u][jj]=='X') break; else a[u][jj]='R';

                for(int jj=v; jj>=0; jj--)

                    if (a[u][jj]=='X') break; else a[u][jj]='R';

                for(int ii=u; ii<n; ii++)

                    if (a[ii][v]=='X') break; else a[ii][v]='R';

                for(int ii=u; ii>=0; ii--)

                    if (a[ii][v]=='X') break; else a[ii][v]='R';

            }

           

            point = 0;

            for(int i=0; i<n; i++) for(int j=0; j<n; j++)

                if (a[i][j]=='.') point++;

           

        }

        cout<<rock<<"\n";

    }

}