题目描述
blablabla
样例
00000
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int g[N][N];
int n,m,t;
int res;
int x1,y1,x2,y2;
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int sx,int sy)
{
if(sx==x2&&sy==y2)
{
res++;
return;
}
st[sx][sy] = true;
for(int i = 0;i<4;i++)
{
int x = sx + dx[i],y = sy + dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(g[x][y]==-1) continue;
if(st[x][y]) continue;
st[x][y] = true;
dfs(x,y);
st[x][y] = false;
}
}
int main()
{
cin >> n >> m >> t;
cin >> x1 >> y1 >> x2 >> y2;
while(t--)
{
int x,y;
cin >> x >> y;
g[x][y] = -1;
}
dfs(x1,y1);
cout << res << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int g[N][N];
int n,m,t;
int res;
int x1,y1,x2,y2;
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int sx,int sy)
{
if(sx==x2&&sy==y2)
{
res++;
return;
}
st[sx][sy] = true;//注意
for(int i = 0;i<4;i++)
{
int x = sx + dx[i],y = sy + dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(g[x][y]==-1) continue;
if(st[x][y]) continue;
st[x][y] = true;
dfs(x,y);
st[x][y] = false;
}
}
int main()
{
cin >> n >> m >> t;
cin >> x1 >> y1 >> x2 >> y2;
while(t--)
{
int x,y;
cin >> x >> y;
g[x][y] = -1;
}
dfs(x1,y1);
cout << res << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int n;
int cnt;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
typedef pair<int,int> PII;
void bfs(int x,int y,bool& flag1)
{
queue<PII> q;
q.push({x,y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
bool flag = true;
for(int i = 0;i<4;i++)
{
int sx = t.first + dx[i],sy = t.second + dy[i];
if(sx<0||sx>=n||sy<0||sy>=n) continue;
if(st[sx][sy]) continue;
if(g[sx][sy]=='.')
{
flag = false;
continue;
}
st[sx][sy] = true;
q.push({sx,sy});
}
if(flag)
{
flag1 = true;
}
}
}
int main()
{
int cnt1 = 0;
cin >> n;
for(int i = 0;i<n;i++) cin >> g[i];
for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
if(g[i][j]=='#' && !st[i][j])
{
bool flag = false;
bfs(i,j,flag);
if(flag)
{
cnt++;
}
cnt1++;
}
}
}
cout << cnt1 - cnt << endl;
return 0;
}