題目描述

Greg has an m × n grid of Sweet Lightbulbs of Pure Coolness he would like to turn on. Initially, some of the?bulbs are on and some are off. Greg can toggle some bulbs by shooting his laser at them. When he shoots?his laser at a bulb, it toggles that bulb between on and off. But, it also toggles every bulb directly below it,and every bulb directly to the left of it. What is the smallest number of times that Greg needs to shoot his?laser to turn all the bulbs on?

?

輸入

The first line of input contains a single integer T (1 ≤ T ≤ 10), the number of test cases. Each test case?starts with a line containing two space-separated integers m and n (1 ≤ m, n ≤ 400). The next m lines each?consist of a string of length n of 1s and 0s. A 1 indicates a bulb which is on, and a 0 represents a bulb which?is off.

?

輸出

For each test case, output a single line containing the minimum number of times Greg has to shoot his laser?to turn on all the bulbs.

?

樣例輸入

復(fù)制樣例數(shù)據(jù)

2 3 4 0000 1110 1110 2 2 10 00

樣例輸出

1 2

?

提示

In the first test case, shooting a laser at the top right bulb turns on all the bulbs which are off, and does not
toggle any bulbs which are on.
In the second test case, shooting the top left and top right bulbs will do the job.

?

題目大意：

先輸入一個(gè)整數(shù)t，代表共有t組測(cè)試，對(duì)于每一組測(cè)試，先輸入兩個(gè)整數(shù)n,m，然后輸入n行m列的0，1表，問(wèn)共需要幾步操作能夠?qū)⑦@個(gè)二維數(shù)組的所有值均變?yōu)?，對(duì)于每一個(gè)操作，假如對(duì)a[i][j]進(jìn)行一次操作，則將a[i][j]，從a[1][j]到a[i][j]，以及從a[i][j]到a[n][j]的所有值取反，即0變1，1變0，問(wèn)最終需要至少幾步操作。

解題思路：

因?yàn)槊看尾僮鲀H會(huì)改變其左邊，下面的值，所以可以從數(shù)組的右上角開(kāi)始遍歷，對(duì)于每一個(gè)0進(jìn)行一次操作，最后輸出操作次數(shù)即可。

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; int hang[500]; int lie[500]; int arr[500][500]; int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;scanf("%d",&t);while(t--) {int n,m;scanf("%d %d",&n,&m);rep(i,1,n) {hang[i]=0;rep(j,1,m) {lie[j]=0;scanf("%1d",&arr[i][j]);}}int ans=0;rep(i,1,n) {lep(j,m,1) {if((arr[i][j]==0&&(hang[i]+lie[j])%2==0)||(arr[i][j]==1&&((hang[i]+lie[j])%2==1))) {ans++;hang[i]++;lie[j]++;}}}printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【模拟】Bulbs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。