题目链接:
https://pintia.cn/problem-sets/994805260223102976/problems/994805265579229184
我的代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1111;
long long g[maxn][maxn];
int cnt = 0;
int M, N, TOL;
bool st[maxn][maxn];
bool istrue[maxn][maxn];
int dx[8] = {1, 1, 1, 0, -1, 1, 0, -1};
int dy[8] = {0, -1, 1, 1, 1, 1, 0, -1};
void judge(int x, int y){
if((abs(g[x + 1][y] - g[x][y]) > TOL) and//如果四周都满足阈值差大于TOL
(abs(g[x - 1][y] - g[x][y]) > TOL) and
(abs(g[x + 1][y + 1] - g[x][y]) > TOL) and
(abs(g[x + 1][y - 1] - g[x][y]) > TOL) and
(abs(g[x - 1][y - 1] - g[x][y]) > TOL) and
(abs(g[x - 1][y + 1] - g[x][y]) > TOL) and
(abs(g[x - 1][y - 1] - g[x][y]) > TOL) and
(abs(g[x][y - 1] - g[x][y]) > TOL) and
(abs(g[x][y + 1] - g[x][y]) > TOL)){ //就符合条件
++cnt; //符合条件的点加一
istrue[x][y] = true; //符合条件,istrue改变状态
}
}
void dfs(int x, int y){
judge(x, y); //判断这个点是否是“一点红”
for(int i = 0; i < 8; i++){//向四周搜索
int xx = dx[i] + x;
int yy = dy[i] + y;
if(xx >= 1 and xx <= M and yy >= 1 and yy <= N and !st[xx][yy]){
st[xx][yy] = true; //搜过了,改变状态
dfs(xx, yy); //继续递归搜索
}
}
}
int main(){
//memset(g, 0x3f3f3f, sizeof g);
cin >> M >> N >> TOL; //分别输入列,行,阈值
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
cin >> g[i][j];
dfs(1, 1); //从起点(1,1)开始搜
if(cnt > 1){ //“一点红”大于一个
cout << "Not Unique";
}
else if(cnt == 0){ //没有“一点红”
cout << "Not Exist";
}
else{ //否则就输出
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++){
if(istrue[i][j]){
printf("(%d, %d): ", i, j);
cout << g[i][j];
}
}
}
return 0;
}
我觉得我的思路挺正确的,就是dfs直接搜,可是最后只能拿到1分,想了很久不知道哪里错了,希望大家能帮忙找出错误下,十分感谢!