POJ-2965

柔光的暖阳◎ 2022-07-16 12:27 82阅读 0赞

<table style="font-family:&quot;Times New Roman&quot;"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      The Pilots Brothers' refrigerator 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td colspan="3"><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;24648</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;9503</td> 
        <td>&nbsp;</td> 
        <td style="font-weight:bold; color:red">Special Judge</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <span></span> 
     <p>The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.</p> 
     <p>There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location&nbsp;<strong>[i, j]</strong>&nbsp;(1 ≤ i, j ≤ 4). However, this also changes states of all handles in row&nbsp;<strong>i</strong>&nbsp;and all handles in column&nbsp;<strong>j</strong>.</p> 
     <p>The task is to determine the minimum number of handle switching necessary to open the refrigerator.</p> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <span></span> 
     <p>The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.</p> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <span></span> 
     <p>The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.</p> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">-+--
----
----
-+--</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">6
1 1
1 3
1 4
4 1
4 3
4 4</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Northeastern+Europe+2004" style="text-decoration:none" rel="nofollow">Northeastern Europe 2004</a>, Western Subregion 
    </div> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <pre><code>//注意一点的是取反偶数次相当于棋子没有变化,取反奇数次相当于变一次
//本题的算法从根部进行枚举,每次枚举此情况后继续往后搜索,判断是否符合情况,如何符合返回,不符合将状态状态还原
#include&lt;stdio.h&gt;
#include&lt;string.h&gt;
#include&lt;iostream&gt;
using namespace std;

int map[5][5];
int x[20]; // 临时路径
int y[20];

int ansX[20]; // 最终路径
int ansY[20];
int ans = 18;

void build()
{
	char c;
	memset(map, 0, sizeof(map));
	for (int i = 0; i &lt; 4; i++)
	{
		for (int j = 0; j &lt; 4; j++)
		{
			cin &gt;&gt; c;
			if (c == '-')
			{
				map[i][j] = 1;    //open
			}
			else
			{
				map[i][j] = 0;
			}
		}
	}
}

void flip(int s)//使此位置的行列进行取反
{
	int x1 = s / 4; // 行
	int y1 = s % 4; // 列

for (int i = 0; i &lt; 4; i++)
	{
		map[i][y1] = !map[i][y1];
		map[x1][i] = !map[x1][i];
	}
	map[x1][y1] = !map[x1][y1];
}

bool complete() // 判断是否达到目标
{
	for (int i = 0; i &lt; 4; i++)
	{
		for (int j = 0; j &lt; 4; j++)
			if (map[i][j] == 0)
			{
				return false;//只要有0就返回false
			}
	}
	return true;//只有全部为1时才返回true
}

void dfs(int s, int b) // 遍历到第 s 个, 翻转了 0个
{
	if (complete())//全部为1时返回
	{
		if (ans &gt; b)
		{
			ans = b;
			for (int i = 1; i &lt;= ans; i++)
			{
				ansX[i] = x[i];
				ansY[i] = y[i];
			}
		}
		return;
	}

if (s &gt;= 16)//遍历到全部取反时返回
	{
		return;
	}

dfs(s + 1, b); //不管第 s 个，直接往下找

flip(s); //翻转第 s 个了再往下找
	x[b + 1] = s / 4 + 1; //临时记录路径【注意】
	y[b + 1] = s % 4 + 1;

dfs(s + 1, b + 1); //翻转第 s 个了再找下一个=&gt;进行了一次判断是否全为1

flip(s); //使用dfs，要考虑到树根时如果还没成功，要回溯；回溯时要把棋子再翻回来，再搜。
}

int main()
{
	build();
	dfs(0, 0);
	printf("%d\n", ans);
	for (int i = 1; i &lt;= ans; i++)
	{
		printf("%d %d\n", ansX[i], ansY[i]);
	}
	return 0;
}
</code></pre> 
     <br> 
     <br> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>