洪泛法BFS
循环接收每组用例，对于每组用例进行如下操作：
- 找到‘@’所在的位置，即起始搜索的点
- 使用DFS搜索地板中的每块瓷砖，如果是黑色，给计数+1，然后像该黑色的上下左右四个方 向继续搜索
注意：在搜索时，如果遇到白色瓷砖，或者该位置已经搜索过了，则停止该位置的搜索
#include<iostream> using namespace std; #include<queue> #include<cstring> const int N=21; typedef pair<int,int> PII; int n,m,x,y; int d[N][N]; char g[N][N]; int bfs(int x,int y) { queue<pair<int,int>> q; q.push({x,y}); memset(d,-1,sizeof d); d[x][y]=0; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int sum=1; while(q.size()) { PII t=q.front(); q.pop(); for(int i=0;i<4;i++) { int gx=t.first+dx[i],gy=t.second+dy[i]; if(gx>=0&&gx<n&&gy>=0&&gy<m&&g[gx][gy]=='.'&&d[gx][gy]==-1) { q.push({gx,gy}); d[gx][gy]=0; sum++; } } } return sum; } int main() { while(cin>>n>>m) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) { cin>>g[i][j]; if(g[i][j]=='@'){ x=i,y=j; } } cout<<bfs(x,y)<<endl; } return 0; }
26进制计数字符串
思路：
题目非常简单，求字典序在s1和s2之间的，长度在len1到 len2的字符串的个数,
我们可以利用ASCII码（字符相减）快速求出两个字符之间含有的字符数
字符有26个，于是我们想到将字符串转化为26进制数，做相减操作，即可求出之间的字符串数
问题一：长度不同如何计算
思路是像计数一样补位相减，如：len2==2时，“a_” 与 “b_” 之间有aa、ab.....az（26个字符串），所以在s1后面补 ‘a’，在s2后面补 ‘z’+1即可
问题二：如何转26进制
为了防止数字太大，采用逐位相减后乘对应进制位；如23 - 17，变为（2-1）*10^1+(3-7)*10^0=6;
利用array数组存储各个位的差值，由题目性质发现字符串第0位，就是进制数第0位，累加和
for (int k = 0; k < i; k++) { result += array[k] * pow(26, 字符串长度 - 1 - k);//加上每一位的差值 }
#include <iostream> #include <string> #include <vector> #include <algorithm> #define N 1000007 #include<math.h> using namespace std; int main() { string s1, s2; int len1, len2; while (cin >> s1 >> s2 >> len1 >> len2) { //将该字符串看成是26进制数，为了简单起见，将s1和s2补长到len2长度 // 注意：s2补的是'z'+1, 因为'z' - 'a' = 25 s1.append(len2 - s1.size(), 'a'); s2.append(len2 - s2.size(), (char)('z' + 1)); // 确认s1和s2的两个字符串每个位置上的差值 vector<int> array(len2); for (int i = 0; i < len2; i++) { array[i]=s2[i] - s1[i]; } // 确认len1和len2之间可组成的不同字符串的个数 long long result = 0;//long long 防止爆int for (int i = len1; i <= len2; i++) {//查找每种长度的字符数 for (int k = 0; k < i; k++) { result += array[k] * pow(26, i - 1 - k);//加上每一位的差值 } } //所有字符串最后都不包含是s2自身，所以最后要减1； cout << (result - 1) % N << endl; } return 0; }
