AcWing 691. bfs + 哈希表
原题链接
简单
代码:
#include <iostream>
#include <queue>
#include <unordered_map>
#define l first
#define r second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int a[N][N];
queue<PII> q;
int n,s;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int res,idx,ans,id;
cin >> n;
int k = 0;
while(n -- )
{
unordered_map<int,PII> mp;
int b[1000010] = {0};
idx = 1;
res = 0;
id = 0;
cin >> s;
for(int i = 0;i < s;i ++ )
for(int j = 0;j < s;j ++ )
{
cin >> a[i][j];
mp[a[i][j]] = {i,j};
}
while(idx <= s * s)
{
int start = idx;
ans = 0;
q.push(mp[idx]);
while(!q.empty())
{
PII x = q.front();
int dx = x.l,dy = x.r;
q.pop();
ans ++ ;
b[a[dx][dy]] = 1;
idx = max(idx,a[dx][dy]);
//if(i == 1 && j == 1) cout << dx << " " << dy << endl;
//cout << s << endl;
if(dx + 1 < s && !b[a[dx + 1][dy]] && (a[dx + 1][dy] == a[dx][dy] + 1))
q.push({dx + 1,dy});
if(dx - 1 >= 0 && !b[a[dx - 1][dy]] && (a[dx - 1][dy] == a[dx][dy] + 1))
q.push({dx - 1,dy});
if(dy + 1 < s && !b[a[dx][dy + 1]] && (a[dx][dy + 1] == a[dx][dy] + 1))
q.push({dx,dy + 1});
if(dy - 1 >= 0 && !b[a[dx][dy - 1]] && (a[dx][dy - 1] == a[dx][dy] + 1))
q.push({dx,dy - 1});
}
if(ans > res)
{
res = ans;
id = start;
}
idx += 1;
}
printf("Case #%d: %d %d\n",++ k,id,res);
}
return 0;
}