题目地址:http://poj.org/problem?id=2965

 /*
题意:4*4的矩形,改变任意点,把所有'+'变成'-',,每一次同行同列的都会反转,求最小步数,并打印方案 DFS:把'+'记为1, '-'记为0
1. 从(1, 1)走到(4, 4),每一点DFS两次(改点反转或不反转);used记录反转的位置
详细解释:http://poj.org/showmessage?message_id=346723
2. 比较巧妙的解法:抓住'+'位置反转,'-'位置相对不反转的特点,从状态上考虑
详细解释:http://poj.org/showmessage?message_id=156561
3. 枚举步骤数(1~16),暴力解法,耗时大
详细解释:http://poj.org/showmessage?message_id=343281
4. 网上还有其他解法:高斯消元,BFS,+位运算等等 注意:反转时十字形中心位置多反转了两次,要再反转一次 我还是DFS写不出来。。。
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
int a[][];
int used[][]; bool ok(void)
{
for (int i=; i<=; ++i)
{
for (int j=; j<=; ++j)
if (a[i][j] == ) return false;
} return true;
} void change(int x, int y)
{
for (int i=; i<=; ++i)
{
a[x][i] = a[x][i] ? : ;
a[i][y] = a[i][y] ? : ;
}
a[x][y] = a[x][y] ? : ;
used[x][y] = used[x][y] ? : ;
} bool DFS(int x, int y)
{
if (x == && y == )
{
if (ok ()) return true; change (x, y);
if (ok ()) return true; change (x, y);
return false;
}
int nx, ny;
if (y == ) nx = x + , ny = ;
else nx = x, ny = y + ; if (DFS (nx, ny)) return true; change (x, y);
if (DFS (nx, ny)) return true; change (x, y);
return false;
} void work(void)
{
if (DFS (, ))
{
int ans = ;
for (int i=; i<=; ++i)
{
for (int j=; j<=; ++j)
{
if (used[i][j]) ans++;
}
}
printf ("%d\n", ans);
for (int i=; i<=; ++i)
for (int j=; j<=; ++j)
if (used[i][j]) printf ("%d %d\n", i, j);
}
else printf ("WA\n");
} int main(void) //POJ 2965 The Pilots Brothers' refrigerator
{
//freopen ("B.in", "r", stdin); char ch;
for (int i=; i<=; ++i)
{
for (int j=; j<=; ++j)
{
scanf ("%c", &ch);
a[i][j] = (ch == '-') ? : ;
//printf ("%d ", a[i][j]);
}
getchar (); //puts ("");
} work (); return ;
} /*
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std; const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
bool con[5][5];
int a[5][5];
struct NODE
{
int x, y;
}node[MAXN]; void work(void)
{
for (int i=1; i<=4; ++i)
{
for (int j=1; j<=4; ++j)
{
if (a[i][j] == 1)
{
con[i][j] = !con[i][j];
for (int k=1; k<=4; ++k)
{
con[i][k] = !con[i][k];
con[k][j] = !con[k][j];
}
}
}
}
int ans = 0;
for (int i=1; i<=4; ++i)
{
for (int j=1; j<=4; ++j)
{
if (con[i][j] == true)
{
ans++; node[ans].x = i; node[ans].y = j;
}
}
}
printf ("%d\n", ans);
for (int i=1; i<=ans; ++i)
printf ("%d %d\n", node[i].x, node[i].y);
} int main(void) //POJ 2965 The Pilots Brothers' refrigerator
{
//freopen ("B.in", "r", stdin); char ch;
for (int i=1; i<=4; ++i)
{
for (int j=1; j<=4; ++j)
{
scanf ("%c", &ch);
a[i][j] = (ch == '-') ? 0 : 1;
}
getchar ();
} work (); return 0;
}
*/ /*
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std; const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[5][5];
struct NODE
{
int x, y;
}node[MAXN];
int k;
bool flag; bool ok(void)
{
for (int i=1; i<=4; ++i)
{
for (int j=1; j<=4; ++j)
if (a[i][j] == 1) return false;
} return true;
} void change(int x, int y)
{
for (int i=1; i<=4; ++i)
{
a[x][i] = !a[x][i];
a[i][y] = !a[i][y];
}
a[x][y] = !a[x][y];
} void DFS(int x, int y, int num, int cnt, int kk)
{
if (num == cnt)
{
flag = ok ();
k = kk;
return ;
}
for (int i=x; i<=4; ++i)
{
int j;
if (i == x) j = y + 1;
else j = 1;
for (; j<=4; ++j)
{
node[kk].x = i;
node[kk].y = j;
change (i, j);
DFS (i, j, num+1, cnt, kk+1);
if (flag) return ;
change (i, j);
}
}
} void work(void)
{
int cnt;
for (cnt=1; cnt<=16; ++cnt)
{
flag = false; k = 0;
DFS (1, 0, 0, cnt, 1);
if (flag) break;
} printf ("%d\n", cnt);
for (int i=1; i<=k - 1; ++i)
printf ("%d %d\n", node[i].x, node[i].y);
} int main(void) //POJ 2965 The Pilots Brothers' refrigerator
{
//freopen ("B.in", "r", stdin); char ch;
for (int i=1; i<=4; ++i)
{
for (int j=1; j<=4; ++j)
{
scanf ("%c", &ch);
a[i][j] = (ch == '-') ? 0 : 1;
}
getchar ();
} work (); return 0;
}
*/

最新文章

  1. CSS Position 定位属性
  2. Android Studio 1.0首次安装遇到的问题,无法下载SDK
  3. (转载)PHP获取客户端、PHP获取服务器相关信息
  4. java 中能否使用 动态加载的类(Class.forName) 来做类型转换?
  5. boost库在工作(39)网络UDP异步服务端之九
  6. hdu 1823 Luck and Love 二维线段树
  7. 【转】Vim学习资料
  8. 妙用perfmon Alert抓dump
  9. [BZOJ1014] [JSOI2008] 火星人prefix (splay &amp; 二分答案)
  10. 2018-2019-2 20165323《网络攻防技术》Exp5 MSF基础应用
  11. [Swift]LeetCode289. 生命游戏 | Game of Life
  12. 关于Java中StringBuffer的capacity问题
  13. AnguarJS中链式的一种更合理写法
  14. uva1330 在一个大的矩阵中寻找面积最大的子矩阵
  15. IOS NSString 用法详解
  16. 【Error】local variable &#39;xxx&#39; referenced before assignment
  17. 2018牛客多校第二场a题
  18. redis启动脚本
  19. 为centos桌面增加在右键中打开终端
  20. windows程序查看可以行文件依赖库

热门文章

  1. Word Amalgamation(枚举 + 排序)
  2. cocos基础教程(7)动作与动画
  3. Spring AOP使用整理:使用@AspectJ风格的切面声明
  4. codeforces 257div2 B. Jzzhu and Sequences(细节决定一切)
  5. MyEclipse安装JS代码提示(Spket插件)
  6. OJ 1188 全排列---康托展开
  7. 试试markdown
  8. mysql中的unsigned
  9. 【leetcode】3Sum Closest
  10. ToDo系列