首页 > 代码库 > 2014东北农大校赛--A. Paint it! (预处理)
2014东北农大校赛--A. Paint it! (预处理)
1141: A.Paint it!
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 13 Solved: 10
[Submit][Status][Web Board]
Description
有一个n*m的棋盘,每个格子只可能是黑和白两种颜色,你可以使用染料将某个格子染成黑色或者白色。求最少需要染多少个格子,
能使当前的棋盘变成类似于国际象棋的棋盘(每个格子临边的四个格子颜色都不与该格子的颜色相同)。
Input
n m(n,m<=100)
接下来输入n行,每行m个0/1字符
Output
最少需要染的格子数
Sample Input
2 2
00
00
2 2
01
10
Sample Output
2
0
HINT
Source
2014农大校赛
解题思路:这题最简单的思路是预处理,就是每个棋盘,只要一个点的状态确定了,其他的就都确定了,所以,总共的状态也就只有两种。不过,只要求出来一种ans,另一种的结果就是n*m - ans,其实最简单的方法也不必要画出所有的棋盘,只要按第一个点的状态,判断所有需要翻转的点,将其翻转并记录个数即可。
AC代码:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; string s[105]; //棋盘 int main(){ // freopen("in.txt", "r", stdin); int n, m; while(scanf("%d%d", &n, &m)!=EOF){ for(int i=0; i<n; i++) cin>>s[i]; int ans = 0; for(int i=0; i<n; i++) for(int j=0; j<m; j++){ if(!i && !j) continue; if(!j){ //特殊处理第一列 if(s[i][j] == s[i-1][j]){ s[i][j] ^= 1; //取反 ans ++; //记录 } } else{ if(s[i][j] == s[i][j-1]){ s[i][j] ^= 1; ans ++; } } } ans = min(ans, m*n - ans); //取两种情况中的最小值 printf("%d\n", ans); } return 0; } /************************************************************** Problem: 1141 User: sxk Language: C++ Result: Accepted Time:1 ms Memory:1692 kb ****************************************************************/
2014东北农大校赛--A. Paint it! (预处理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。