还有很大提升空间的代码

寻找最大全1正方形，返回边长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <string>
using namespace std;
int findMatrix(string matrix, int startLength, int column, int row)
{
    int currentLength = startLength;
    int totalPixel=1;
    for (int i=0;i<=column-currentLength;i++)
    {
        for (int j=0; j<=row-currentLength; j++)
        {
            totalPixel = currentLength * currentLength;
            // 外边两层循环便利所有起点
            // 下边两层循环，找到以（j,i）为左上角起点的正方形
            for (int m=0; m<currentLength; m++)
            {
                for (int n=0; n<currentLength; n++)
                {
                    if (matrix[j*column+i+n*column+m]=='0')
                    {
                        break;
                    }
                    if(matrix[j*column+i+n*column+m]=='1')
                    {
                        totalPixel -=1;
                        if (totalPixel==0)
                        {
                            return currentLength;
                        }
                    }
                }
            }

        }
    }
    if (totalPixel!=0)
    {
        // 递减边长
        if (currentLength>1)
        {
            return findMatrix(matrix, currentLength-1, column, row);
        }
        else
        {
            return 1;
        }
    }
    else
    {
        return currentLength;
    }
}



int main()
{
    int sideLength;
    int row,column;
    cin >> row >> column;
    if(row >= column)
    {
        sideLength = column;
    }
    else
    {
        sideLength = row;
    }
    int total = row * column;
    string matrix;
    for(int j=0;j<row;j++)
    {
        for(int i=0;i< column;i++)
        {
            string number;
            cin >> number;
            matrix.append(number);
        }
    }
    bool allZero = true;
    for (int m=0; m<total; m++)
    {
        if(matrix[m]=='1')
        {
            allZero = false;
            break;
        }
    }
    if (allZero)
    {
        // 全0
        cout << 0 << endl;
        return 0;
    }
    int answer = findMatrix(matrix, sideLength, column, row);
    cout << answer << endl;
    return 0;
}

测试结果如图
pic

寻找B是否能到达H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <string>
using namespace std;

string checkDirection(string matrix,int position,int row, int column)
{
	int total = row * column;
	string direction="0000";
	if(position-column>=0)
	{
		direction[0] = '1';
	}
	if((position+1)<=(total-1) && (position+1)%column!=0)
	{
		direction[1] = '1';
	}
	if((position+column)<=(total-1))
	{
		direction[2] = '1';
	}
	if((position-1)>=0 && (position%column)!=0)
	{
		direction[3] = '1';
	}
	return direction;
}
string hasRoad(string matrix,int position,int row, int column,char *coverMap)
{
	coverMap[position] = '0';
	string direction;
	direction = checkDirection(matrix,position,row,column);
	int index[4] = { position-column, position+1, position+column, position-1 };
	for(int i=0;i<4;i++)
	{
		if(direction[i]=='1')
		{
			if(matrix[index[i]]=='-' || matrix[index[i]]=='H')
			{
				direction[i]='1';
			}
			if(matrix[index[i]]=='#' || matrix[index[i]]=='B')
			{
				direction[i]='0';
			}
			if(coverMap[index[i]]=='0')
			{
				direction[i]='0';
			}
		}
	}
	return direction;


}
char findHome(string matrix,int startPoint,int row, int column,char *coverMap)
{
	char found = 'N';
	string direction = hasRoad(matrix,startPoint,row,column,coverMap);
	int index[4] = { startPoint-column, startPoint+1, startPoint+column, startPoint-1 };
	for(int i=0;i<4;i++)
	{
		if(direction[i]=='1')
		{
			// cout << "startPoint" << startPoint << endl;
			if(matrix[index[i]]=='H')
			{
				return 'Y';
			}
		}
	}
	for(int n = 0;n<4;n++)
	{
		if(direction[n]=='1')
		{
			found = findHome(matrix,index[n],row,column,coverMap);
			if(found=='Y')
			{
				return 'Y';
			}
	
		}
	}
	return found;
}
int main()
{
	int row,column;
	cin >> row >> column;
	int total = row*column;
	char *cover;
	cover = new char(total);
	string forest;
	int positionB = 0;
	int positionH = 0;
	for(int j=0;j<row;j++)
    {
        for(int i=0;i< column;i++)
        {
            string road;
            cin >> road;
			if(road=="-" || road=="H")
			{
				cover[j * column + i] = '1';
			}
			else
			{
				cover[j * column + i] = '0';
			}
			if(road=="B")
			{
				positionB = j * column + i;
			}
			if(road=="H")
			{
				positionH = j * column + i;
			}
            forest.append(road);
        }
    }
	cout << findHome(forest,positionB,row,column,cover) << endl;

	system("pause");
	return 0;
}

运行结果如图
pic
pic
仍然存在的问题是：没有选择最短路径，有时候Visual Studio会出错
pic

本文标题:还有很大提升空间的代码

文章作者:Orange

发布时间:2016-06-26, 23:12:26

最后更新:2016-06-26, 23:14:03

原始链接:http://learningpro.github.io/2016/06/26/还有很大提升空间的代码/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 寻找最大全1正方形，返回边长
  2. 2. 寻找B是否能到达H
,