4.3西山居笔试题编程题

两题都AC了，老费力了，由于前面很拉，所以这里我尽力做到了全A，希望能进面吧

顺便分享一下本地的代码：

编程题1：

剑指offer中等难度原题，动态规划的，很简单不说了

编程题2：

开心消消乐咯，找一次能消除最多方块的位置进行消除，直到消除完需要多少步，每一步是那个位置；

（近百行代码用模拟暴力做的，实在不知道怎么优化）

/*
m*n个方格
0 表示无方块， 1表示有方块
指定x,y位置消除这一行一列
每次指定最多可消除的位置，并求多少次能消除完


输出多少步
3 4
0 1 0 0
0 1 0 1
0 1 1 1

输出消除位置x,y;
2
3,2
2,4
*/


#include <bits/stdc++.h>
using namespace std;


int m = 0, n = 0;//棋盘宽高
int maxi = 0, maxj = 0;//消除最多方块的位置
int res[100][100];//存储每次消除方块的位置 
bool a[100][100];//存储棋盘 
int  b[100][100];//存储对应位置的最大可消除方块数量 


//计算当前方块可消除数 
int f(int x, int y){
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(a[x][i]) ans++;
	}
	for(int i = 1; i <= m; i++){
		if(a[i][y]) ans++;
	}
	return ans;
}


//计算是否消除完毕 , true 表示还有， false 表示没了 
bool isT(){
	bool flag = false;
	for(int i = 1; i <= m; i++){
    	for(int j = 1; j <= n; j++){
    		if(a[i][j]){
    			flag = true;
			}
		}
	}
	return flag;
} 


int main(){
	cin>>m>>n;
	for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin>>a[i][j];
    
	for(int i = 0; i < 100; i++){
		for(int j = 0; j < 100; j++){
        	res[i][j] = 0;
        	b[i][j] = 0; 
		}
	} 
            
	//计算消除最多的方块的位置,并消除 后把ans +1 
	int k = 0, retans = 0;
	while(isT()){
		int maxnum = 0;
		
		for(int i = 1; i <= m; i++){
			for(int j = 1; j <= n; j++){
        		if(a[i][j]){
        			b[i][j] = f(i, j);
        			if(b[i][j] > maxnum){
        				maxnum = b[i][j];
        				maxi = i;
        				maxj = j;
					}
				}
			}
		}
		res[k][0] = maxi;
		res[k][1] = maxj;
		k++;	
		for(int i = 1; i <= n; i++)
			if(a[maxi][i]) a[maxi][i] = 0;
		for(int i = 1; i <= m; i++)
			if(a[i][maxj]) a[i][maxj] = 0;
		retans++;
	}
	cout<<retans<<endl;
	for(int i = 0; i < 100; i++){
    		if(res[i][0] != 0 || res[i][1] != 0){
    			cout<< res[i][0] << "," << res[i][1] << endl;
			} else if(res[i][0] == 0 || res[i][1] == 0) break;
	}
	return 0;
}