Test 2016"/>
【Test 2016
【题目描述】
给出一个 n×n 的矩阵,每个格子里有一盏灯,当你妄图去改变 (i,j) 这个格子里的灯的开关状态时, (i−1,j −1),(i−1,j + 1),(i + 1,j −1),(i + 1,j + 1) 这四个格子里的灯也会同时被你改变。
给出 n^2 盏灯的初始状态,询问是否存在一种方案可以关掉所有的灯,如果存在则输出’Y’,否则输 出’N’【Sample Input】
5
1 0 0 0 1
1 0 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 0 1【Sample Output】
Y【数据范围】
对于60% 的数据,n<=4。
对于100% 的数据,n<=10。
【题解】看到数据范围很小我们当然想到搜索。
{60%} 搜索
{100%} 枚举第一行的操作情况,按顺序从第一行向下做操作,对于当前行的某个点(i,j),它的状态由于(i-1,j-1)的已确定,也已经确定,因为只有这个点能影响到(i-1,j-1)的状态。故而这个点是否进行操作取决于(i-1,j-1)是否需要一次操作。当然做每一行时要保证(i-1,n)是关闭的。
#include <cstdio>
int n,a[15][15],b[15][15],r[15];void rev(int i,int j){b[i][j]^=1;b[i-1][j-1]^=1;b[i-1][j+1]^=1;b[i+1][j-1]^=1;b[i+1][j+1]^=1;}bool work(){if (!r[1] && r[2] && !r[3] && r[4])r[5]=0;for (int i=1;i<=n;++i)for (int j=1;j<=n;++j) b[i][j]=a[i][j];for (int i=1;i<=n;++i)if (r[i]) rev(1,i);for (int i=2;i<=n;++i){for (int j=2;j<=n;++j)if (b[i-1][j-1]) rev(i,j);if (b[i-1][n]) return false;}for (int i=1;i<=n;++i)if (b[n][i]) return false;return true; }bool dfs(int x){if (x>n) return work();r[x]=0;if (dfs(x+1)) return true;r[x]=1;if (dfs(x+1)) return true;return false;}
int main()
{scanf("%d\n",&n);for (int i=1;i<=n;++i)for (int j=1;j<=n;++j) scanf("%d",&a[i][j]);if (dfs(1)) printf("Y");else printf("N");return 0;
}
【题外话】这道题可以有很多变形,比如把操作的影响改成影响上下左右。方法同上~
更多推荐
【Test 2016
发布评论