{"id":6275,"date":"2020-02-09T00:33:43","date_gmt":"2020-02-09T08:33:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6275"},"modified":"2020-02-11T22:22:24","modified_gmt":"2020-02-12T06:22:24","slug":"leetcode-1349-maximum-students-taking-exam","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1349-maximum-students-taking-exam\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1349. Maximum Students Taking Exam"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1349. Maximum Students Taking Exam - \u5237\u9898\u627e\u5de5\u4f5c EP307\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/QJvCYx1eGxE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given a&nbsp;<code>m&nbsp;* n<\/code>&nbsp;matrix&nbsp;<code>seats<\/code>&nbsp;&nbsp;that represent seats distributions&nbsp;in a classroom.&nbsp;If a seat&nbsp;is&nbsp;broken, it is denoted by&nbsp;<code>'#'<\/code>&nbsp;character otherwise it is denoted by a&nbsp;<code>'.'<\/code>&nbsp;character.<\/p>\n\n\n\n<p>Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting&nbsp;directly in front or behind him. Return the&nbsp;<strong>maximum&nbsp;<\/strong>number of students that can take the exam together&nbsp;without any cheating being possible..<\/p>\n\n\n\n<p>Students must be placed in seats in good condition.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/29\/image.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> seats = [[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],\n&nbsp;               [\".\",\"#\",\"#\",\"#\",\"#\",\".\"],\n&nbsp;               [\"#\",\".\",\"#\",\"#\",\".\",\"#\"]]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Teacher can place 4 students in available seats so they don't cheat on the exam. \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> seats = [[\".\",\"#\"],\n&nbsp;               [\"#\",\"#\"],\n&nbsp;               [\"#\",\".\"],\n&nbsp;               [\"#\",\"#\"],\n&nbsp;               [\".\",\"#\"]]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> Place all students in available seats. \n\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> seats = [[\"#\",\".\",\"<strong>.<\/strong>\",\".\",\"#\"],\n&nbsp;               [\"<strong>.<\/strong>\",\"#\",\"<strong>.<\/strong>\",\"#\",\"<strong>.<\/strong>\"],\n&nbsp;               [\"<strong>.<\/strong>\",\".\",\"#\",\".\",\"<strong>.<\/strong>\"],\n&nbsp;               [\"<strong>.<\/strong>\",\"#\",\"<strong>.<\/strong>\",\"#\",\"<strong>.<\/strong>\"],\n&nbsp;               [\"#\",\".\",\"<strong>.<\/strong>\",\".\",\"#\"]]\n<strong>Output:<\/strong> 10\n<strong>Explanation:<\/strong> Place students in available seats in column 1, 3 and 5.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>seats<\/code>&nbsp;contains only characters&nbsp;<code>'.'&nbsp;and<\/code><code>'#'.<\/code><\/li><li><code>m ==&nbsp;seats.length<\/code><\/li><li><code>n ==&nbsp;seats[i].length<\/code><\/li><li><code>1 &lt;= m &lt;= 8<\/code><\/li><li><code>1 &lt;= n &lt;= 8<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: DFS (TLE)<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(2^(m*n)) = O(2^64)<br>Space complexity: O(m*n)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP<\/strong><\/h2>\n\n\n\n<p>Since how to fill row[i+1] only depends on row[i]&#8217;s state, we can define<\/p>\n\n\n\n<p>dp[i][s] as the max # of students after filling i rows and s (as a binary string) is the states i-th row.<\/p>\n\n\n\n<p>dp[i+1][t] = max{dp[i][s] + bits(t)} if row[i] = s &amp;&amp; row[i +1] = t is a valid state.<\/p>\n\n\n\n<p>Time complexity: O(m*2^(n+n)*n) = O(2^22)<br>Space complexity: O(m*2^n) = O(2^11) -&gt; O(2^n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxStudents(vector<vector<char>>& seats) {\n    int m = seats.size();\n    int n = seats[0].size();\n    vector<vector<int>> dp(m + 1, vector<int>(1 << n));    \n    for (int i = 0; i < m; ++i)\n      for (int l = 0; l < (1 << n); ++l)\n        for (int c = 0; c < (1 << n); ++c) {\n          bool flag = true;\n          for (int j = 0; j < n &#038;&#038; flag; ++j) {\n            if (!(c &#038; (1 << j))) continue;\n            if (seats[i][j] == '#') flag = false;            \n            bool l = j == 0 ? false : (c &#038; (1 << (j - 1)));\n            bool r = j == n - 1 ? false : (c &#038; (1 << (j + 1)));\n            bool ul = (j == 0 || i == 0) ? false : (l &#038; (1 << (j - 1)));\n            bool ur = (j == n - 1 || i == 0) ? false : (l &#038; (1 << (j + 1)));\n            if (l || r || ul || ur) flag = false;\n          }\n          if (flag)\n            dp[i + 1][c] = max(dp[i + 1][c], dp[i][l] + __builtin_popcount(c));\n        }\n    return *max_element(begin(dp[m]), end(dp[m]));\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxStudents(vector<vector<char>>& seats) {\n    const int m = seats.size();\n    const int n = seats[0].size();\n    vector<int> s(m + 1);    \n    for (int i = 1; i <= m; ++i)\n      for (int j = 0; j < n; ++j)\n        s[i] |= (seats[i - 1][j] == '.') << j;\n    \n    vector<vector<int>> dp(m + 1, vector<int>(1 << n));        \n    for (int i = 1; i <= m; ++i)      \n      for (int c = s[i];;c = (c - 1) &#038; s[i]) {\n        if (c &#038; (c >> 1)) continue;\n        for (int l = s[i - 1];;l = (l - 1) & s[i - 1]) {\n          if (!(l & (c >> 1)) && !((l >> 1) & c))\n            dp[i][c] = max(dp[i][c], dp[i - 1][l] + __builtin_popcount(c));          \n          if (l == 0) break;\n        }\n        if (c == 0) break;\n      }\n    return *max_element(begin(dp[m]), end(dp[m]));\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;m&nbsp;* n&nbsp;matrix&nbsp;seats&nbsp;&nbsp;that represent seats distributions&nbsp;in a classroom.&nbsp;If a seat&nbsp;is&nbsp;broken, it is denoted by&nbsp;&#8216;#&#8217;&nbsp;character otherwise it is denoted by a&nbsp;&#8216;.&#8217;&nbsp;character. Students can see the answers&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[549,18,217,550],"class_list":["post-6275","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-binary-mask","tag-dp","tag-hard","tag-state","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6275"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6275\/revisions"}],"predecessor-version":[{"id":6299,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6275\/revisions\/6299"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}