AC代码在最下面。
做题记录:
昨天没过的:
今天重新理了下思路:
水坑问题思路:用双重for循环搜索'W',搜到后cnt++然后用dfs搜索这个水坑占的所有格子,标记或换成'.',以免重复搜索,然后继续搜索下一个'W'
主要是写好dfs函数
把格子标记完又保证能搜到其他格子就有点麻烦
要搜索八个方向
错误代码:
#include#include using namespace std; int n,m; char s[100][100]; int cnt=0; int vis[100][100]; void dfs(int x,int y) { vis[x][y]=1; for(int i=-1;i<=1;i++) { for(int j=-1;j<=1;j++) { int nx=x+i; int ny=y+j; if(s[nx][ny]=='W'&&nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]) { dfs(nx,ny); } } } return; } int main() { cin>>n>>m; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>s[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]=='W'&&!vis[i][j]) { dfs(i,j); cnt++; } } } cout< 觉得没啥问题了,不好改哪,就把数组开大了点,过了
OK,下面是完全正确的代码:
#include#include using namespace std; int n,m; char s[110][110]; int cnt=0; int vis[110][110]; void dfs(int x,int y) { vis[x][y]=1; for(int i=-1;i<=1;i++) { for(int j=-1;j<=1;j++) { int nx=x+i; int ny=y+j; if(s[nx][ny]=='W'&&nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]) { dfs(nx,ny); } } } return; } int main() { cin>>n>>m; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>s[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j]=='W'&&!vis[i][j]) { dfs(i,j); cnt++; } } } cout<
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)