74 solutions

  • -2
    @ 2025-6-29 19:32:54
    #include<bits/stdc++.h>
    using namespace std;
    int N;
    char board[25][25][3];
    set<int> s;
    bool beenthere[25][25][19683];
    int pow3[10];
    bool test_win(int b)
    {
    	int cells[3][3]; //得到当前b表示的这个格子
    	for(int i=0;i<3;i++)
    	{
    		for(int j=0;j<3;j++)
    		{
    			cells[i][j]=b%3;
    			b/=3;
    		}
    	}
    	for(int r=0;r<3;r++) //判断行是否满足MOO或OMM
    	{
    		if(cells[r][0]==1&&cells[r][1]==2&&cells[r][2]==2) return true; 
    		if(cells[r][0]==2&&cells[r][1]==2&&cells[r][2]==1) return true;
    	}
    	for(int c=0;c<3;c++)//判断列是否满足MOO或OMM
    	{
    		if(cells[0][c]==1&&cells[1][c]==2&&cells[2][c]==2) return true;
    		if(cells[0][c]==2&&cells[1][c]==2&&cells[2][c]==1) return true;
    	}
    	//判断对角线是否满足MOO或OMM
    	if(cells[0][0]==1&&cells[1][1]==2&&cells[2][2]==2) return true;
    	if(cells[0][0]==2&&cells[1][1]==2&&cells[2][2]==1) return true;
    	if(cells[2][0]==1&&cells[1][1]==2&&cells[0][2]==2) return true;
    	if(cells[2][0]==2&&cells[1][1]==2&&cells[0][2]==1) return true;
    	return false;
    }
    void dfs(int i,int j,int b) //走到了(i,j这个位置,当前状态是b)
    {
    	if(beenthere[i][j][b]) return ; //出现过直接结束
    	beenthere[i][j][b]=true; //标记已经出现过
    	if(test_win(b))
    	{
    		s.insert(b);
    		return ;	
    	} 
    	if(board[i][j][0]=='M'||board[i][j][0]=='O') //可以加了一位
    	{
    		int r=board[i][j][1]-'1',c=board[i][j][2]-'1',idx=r*3+c; 
    		//  行                   列                    扩展了要填的位置
    		int current_char=(b/pow3[idx])%3; //当前的数字
    		if(current_char==0) //当前位置上是空的
    		{
    			int new_char=board[i][j][0]=='M'?1:2; //得到当前位置上的数字
    			b=(b%pow3[idx])+new_char*pow3[idx]+(b-b%pow3[idx+1]);
    			// 前面的部分    更新的状态         后面的部分
    		
    		}
    	}
    	if(board[i-1][j][0]!='#') dfs(i-1,j,b); //上
        if(board[i+1][j][0]!='#') dfs(i+1,j,b); //下
    	if(board[i][j-1][0]!='#') dfs(i,j-1,b); //左
    	if(board[i][j+1][0]!='#') dfs(i,j+1,b); //右
    }
    int main()
    {
    	int bess_i,bess_j,bstate=0;
    	pow3[0]=1;
    	for(int i=1;i<=9;i++) pow3[i]=pow3[i-1]*3; //pow3[i]表示3的i次方
    	cin>>N;
    
    	for(int i=0;i<N;i++)
    	{
    		for(int j=0;j<N;j++)
    		{
    		    cin>>board[i][j][0]>>board[i][j][1]>>board[i][j][2]; //board表示(i,j)的格子状态
    			if(board[i][j][0]=='B') //位置
    			{
    				bess_i=i,bess_j=j;
    			}
    		}
    	}	//return 0;
    	dfs(bess_i,bess_j,bstate); //开始搜索
    	cout<<s.size(); //方案的数目
    	return 0;
    }
    

    Information

    ID
    838
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    2
    Tags
    # Submissions
    371
    Accepted
    104
    Uploaded By