去哪兒筆試：座位安排問(wèn)題

題目描述

假設(shè)一個(gè)教室有m * n 個(gè)座位，每個(gè)座位上可以座一個(gè)學(xué)生。前提是座位沒(méi)有壞掉，沒(méi)壞的座位用’.’表示，壞掉的座位用’x’表示。

現(xiàn)在要在這個(gè)教室安排考試，由于坐在(x,y)位置上的同學(xué)能夠抄到(x-1,y-1)、(x-1,y+1)、(x,y-1)、(x,y+1)的同學(xué)，所以要把他們分開(kāi)安排。現(xiàn)在讓我們計(jì)算出，這個(gè)教室能夠最多安排多少人。

輸入樣例

2 3
…
…

輸出樣例

4

思路

從左上角的位置開(kāi)始安排

• 首先判斷是不是壞掉的座位，如果是則不能安排人
• 然后判斷能不能抄襲到別人

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();sc.nextLine();char[][] arr = new char[m][n];for(int i = 0; i < m; i++) {String line = sc.nextLine();char[] c = line.toCharArray(); for(int j = 0; j < n; j++) {arr[i][j] = c[j]; }}int[][] dp = new int[m+2][n+2];int count = 0;for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(arr[i-1][j-1] == 'x') { // 如果座位壞掉了continue;}// 判斷能不能抄襲到別人if(dp[i-1][j-1] == 0 && dp[i-1][j+1] == 0 && dp[i][j-1] == 0 && dp[i][j+1] == 0) {dp[i][j] = 1;count++;}}}for(int i = 0; i <= m; i++) {for(int j = 0; j <= n; j++) {System.out.print(dp[i][j]+" ");}System.out.println();}System.out.println(count);}}

總結(jié)

以上是生活随笔為你收集整理的去哪儿笔试：座位安排问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。