Untitled
plain_text
2 months ago
1.1 kB
5
Indexable
Never
#include <iostream> #define MAX 99999999 using namespace std; int n; char board[5][5]; int ans; bool check(int x, int y){ for(int i=x; i<n; i++){ if(board[i][y]=='#') return false; if(board[i][y]=='X') break; } for(int i=x-1; i>=0; i--){ if(board[i][y]=='#') return false; if(board[i][y]=='X') break; } for(int i=y; i<n; i++){ if(board[x][i]=='#') return false; if(board[x][i]=='X') break; } for(int i=y-1; i>=0; i--){ if(board[x][i]=='#') return false; if(board[x][i]=='X') break; } return true; } void backTrack(int num){ ans = max(ans, num); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(board[i][j]=='.' && check(i, j)){ board[i][j]='#'; backTrack( num+1); board[i][j]='.'; } } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin >> board[i][j]; } } ans=0; backTrack( 0); cout << "Case #" << tc << endl; cout << ans << endl; } return 0; }