UVa 639 Don't Get Rooked

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <iostream>

 4  #include <algorithm>

 5  #include <string.h>

 6  using namespace std;

 7  int n;

 8  int board[7][7];

 9  bool check(int x,int y)

10  {

11      if(board[x][y]==1 || board[x][y]==2) return false;

12      else if(board[x][y]==0)

13      {

14          for(int i=x; i>=0; i--)

15          {

16              if(board[i][y]==2) return false;

17              else if(board[i][y]==1) break;

18          }

19          for(int i=x; i<n; i++)

20          {

21              if(board[i][y]==2) return false;

22              else if(board[i][y]==1) break;

23          }

24          for(int j=y; j>=0; j--)

25          {

26              if(board[x][j]==2) return false;

27              else if(board[x][j]==1) break;

28          }

29          for(int j=y; j<n; j++)

30          {

31              if(board[x][j]==2) return false;

32              else if(board[x][j]==1) break;

33          }

34          return true;

35      }

36  }

37  int tmp=0;

38  int put(int x,int y,int num)

39  {

40      tmp=max(num,tmp);

41      for(int i=x; i<n; i++)

42      {

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

44          {

45              if(check(i,j) && (x!=i || y!=j) && ((i>x && j>=0) ||(i==x&& j>y)))

46              {

47                  board[i][j]=2;

48                  put(i,j,num+1);

49                  board[i][j]=0;

50                  put(i,j,num);

51              }

52          }

53      }

54  }

55  int main()

56  {

57      while(cin>>n && n!=0)

58      {

59          tmp=0;

60          memset(board,0,sizeof(board));

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

62          {

63              string str;

64              cin>>str;

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

66              {

67                  if(str[j]=='.') board[i][j]=0;

68                  else if(str[j]=='X') board[i][j]=1;

69              }

70          }

71          int num=0,num1=0;

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

73          {

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

75              {

76                  if(board[i][j]==0)

77                  {

78                      board[i][j]=2;

79                      put(i,j,1);

80                      board[i][j]=0;

81                      put(i,j,0);

82                      break;

83                  }

84              }

85          }

86          cout<<tmp<<endl;

87      }

88      return 0;

89  }