Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Java

Posted by 201722362014068 at 2019-03-22 01:45:55 on Problem 1321
import java.util.Scanner;

public class Main {

	
	private static char[][] c;//记录信息
	private static int sum;//总共的方案
	private static int k;//棋盘的棋子个数
	private static int n;//棋盘的大小
	private static int m;//已放入棋盘的棋子数目
	private static int[] visit;//每一列是否被放过

	public static void dfs(int line) {
		if(m==k) {
			sum++;
			return;
		}
		if(line>=n) {
			return;
		}
		for(int j=0;j<n;j++) {
			if((visit[j]==0)&&(c[line][j]=='#')){
				visit[j]=1;
				m=m+1;
				dfs(line+1);
				visit[j]=0;
				m=m-1;
			}
			
		}
		dfs(line+1);
	}
	
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		while((n=in.nextInt())!=-1&&(k=in.nextInt())!=-1) {
			c = new char[n][n];
			sum=0;
			m=0;
			visit=new int[n];
			for(int i=0;i<visit.length;i++) {
				visit[i]=0;
			}
			for(int i=0;i<n;i++) {
				String s = in.next();
				char[] p = s.toCharArray();
				for(int j=0;j<p.length;j++) {
					c[i][j] = p[j];
				}
			
			}
			dfs(0);
			System.out.println(sum);
			
	  	  }
		
		}

	}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator