CareerCup

public int numOfWay (char [][] ch){
		return solve(ch, 0);
	}
	
	private int solve (char [][] ch , int x){
		if (x >= ch.length) {
			return 1 ;
		}
		int  total = 0;		
		for (int i = 0 ; i < ch[0].length ;++i) {
			if(ch[x][i] == '*') {
				continue ;
			}
			if (isValid(ch, x, i)) {
				ch[x][i] = 'b' ;
				total += solve(ch, x + 1);
				ch[x][i] = '.' ;	
			}			
		}		
		return total ;
	}
		
	private boolean isValid (char [][] ch, int i , int j) {
		int x = i - 1 ;
		int y = j - 1 ;
		//left corner ;
		while (x >= 0 && y >= 0 && ch[x][y] != '*') {
			if (ch[x][y] == 'b') {
				return false ;
			}
			x--;
			y--;
		}
		//right corner;
		x = i - 1 ;
		y = j + 1 ;
		while (x >=0 && y < ch[0].length && ch[x][y] != '*') {
			if (ch[x][y] == 'b') {
				return false ;
			}
			x--;
			y++;
		}						
		return true ;

}

UPD: I optimized my code, now it works in O(N*2^N*2^N). I added UPD part at the end of my old explanations.

Here's my not-optimal DP solution:
It's O(N*2^(4*N)), which for this problem is O(10*2^40)

dp[i][state1][state2] = number of ways of putting bishops in rows>=i while state1 shows the state of primary diagonals and state2 show the state of secondary diagonals.

with one iteration I free those diagonals that are blocked by cells of current row.
and then I add answer of putting a bishop in current row and going to next row.


UPD:

I realized that when we are at row i, we actually don't need to know about state of every diagonal. all we nned is to know about the diagonals which can threat current row.
So we just need to know about N primary diagonals and N secondary diagonals. So the total complexity is N*2^N*2^N which is 10*2^20 ~ 10^7 which is fine for this problem.

/*
MehrdadAP
Count number of ways of putting exactly one bishop in a chess with obstacles.

O(N*2^N*2^N)

*/

#include <iostream>
#include <string.h>

using namespace std;

const int maxn = 10;
int N,M;
int dp[maxn][1<<maxn][1<<maxn];
char grid[maxn][maxn];

int solve(int row,int state1,int state2)
{
	
	if (row==N) return 1;
	
	//we actually don't need all the information of
	//state1 and state2, so we can reduce them to ss1 and ss2
	
	//to make the implementation easier, I use state1 and state2 
	//when pass it to next row, but for stoing in dp table, I use
	//ss1 and ss2 

	int ss1=0,ss2=0;
	for (int col=0;col<M;col++){
		int diagInd = ( row<=col ? col-row : row-col+M-1);
		int diagInd2= row+col;

		if ((state1 & (1<<diagInd))!=0)
			ss1 |=(1<<col);

		if ((state2 & (1<<diagInd2))!=0)
			ss2 |=(1<<col);
	}

	int &ref = dp[row][ss1][ss2];
	if (ref!=-1)
		return ref;


	for (int col=0;col<M;col++){
		int diagInd = ( row<=col ? col-row : row-col+M-1);
		int diagInd2= row+col;

		if (grid[row][col] == '*'){
			state1 &= ~(1<< diagInd);
			state2 &= ~(1<<diagInd2);
		}
	}


	int ans=0;
	for (int col=0;col<M;col++){
		int diagInd = ( row<=col ? col-row : row-col+M-1);
		int diagInd2= row+col;

		if (grid[row][col]== '*') continue;

		if ((state1 & (1<<diagInd))==0 && (state2 & (1<<diagInd2))==0 ){
			ans+= solve(row+1,state1 | (1<<diagInd) , state2 | (1<< diagInd2));
		}
	}

	//cout << row << " " << state << " " <<ans << endl;
	return ref = ans;
}


int main()
{

	while (cin >> N >> M){

		for (int i=0;i<N;i++)
			for (int j=0;j<M;j++)
				cin >> grid[i][j];

		memset(dp,-1,sizeof dp);

		cout << solve(0,0,0) << endl;

	}
	


	return 0;
}

Its like n queen problem with extra obstracles condition added.