NC14622. Piglet treasure hunt Series 2
描述
Once there was a pig, which was very fond of treasure hunting. One day, when it woke up, it found itself in a strange land of treasure. As for how to come in, or how to go out, no ways to know. Sad.
The good news is, it was lucky that it got the treasure map.
But there is a bad news too, this map is an encrypted map.
You can think of it as a matrix of R*C. Each grid is a number of Hexadecimal（十六进制）, that is the number is between {‘0’,’1’,…’9’,’A’,’B’,…,’F’}, and the 4 length Binary number(4位二进制数) corresponding is the real treasure map.
For example, the number '0' on the encrypted graph represents the actual map ‘0000’, and '1' represents the actual map ‘0001’, ... The 'A' represents the actual map ‘1010’, and 'F' represents the actual map ‘1111’.
The owner of the treasure is very clever, he build some insuperable wall in the treasure to avoid stealing, we use ‘0’ to describe it. Obviously ‘1’ indicated that this grid bury exactly one diamond.
The pig can only walk up to four adjacent squares in the upper, lower, left and right directions at a time. Wherever it goes, it will dig out the diamond in this grid(if there is diamond buried in the grid) and put the diamond in its own package.
Though it has got the map, but doesn't know where it is in the peach blossom trap now, that means it could be at any ‘.’ in the matrix. It finds you smart to tell it how many diamonds it will get at most.
输入描述
Multiple groups of test case. (no more than 10 groups. )
The first line of each group contains two numbers R and C,(0<=R, C<=3000), representing the number of rows and the number of columns of peach blossom trap, respectively. Stop the program when R and C are both 0.
Then there are next R lines, each line contains C characters, describe as above.
It is guarantee all the input is legal.
输出描述
For each test case, output the answer on each line, representing the most number of diamonds can be obtained by the pig.
示例1
输入:
5 2 E8 23 52 78 01 3 1 0 4 0 0 0
输出:
6 1
说明:
In the first example, the real treasure map is:C++14(g++5.4) 解法, 执行用时: 4378ms, 内存消耗: 24540K, 提交时间: 2018-05-16 01:27:09
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=3e3+1;
bitset <MAXN*4> a[MAXN];
int row,col;
char str[MAXN];
int dirx[4]={0,0,-1,1};
int diry[4]={1,-1,0,0};
int trans(char x){
if(x<='9'&&x>='0') return x-'0';
return 10+x-'A';
}
struct node{int x,y;}beg,in,out;
int BFS(){
queue<node>Q;
Q.push(beg);
int res=0;
while(!Q.empty()){
res++;
out=Q.front();Q.pop();
for(int i=0;i<4;i++){
in.x=out.x+dirx[i];
in.y=out.y+diry[i];
if(in.x<0||in.y<0||in.x>=row||in.y>=col||a[in.x][in.y]==0) continue;
a[in.x][in.y]=0;Q.push(in);
}
}
return res;
}
int main(){
// freopen("in.txt","r",stdin);
while(~scanf("%d %d",&row,&col)&&(row||col)){
getchar();
for(int i=0;i<row;++i){
for(int j=0;j<col;++j){
int num=trans(getchar());
for(int k=3;k>=0;k--){
if(num&1)a[i][j*4+k]=1;
else a[i][j*4+k]=0;
num>>=1;
}
}
getchar();
}
col<<=2;
int ans=0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(a[i][j]){
beg.x=i;beg.y=j;a[i][j]=0;
ans=max(BFS(),ans);
}
}
}
printf("%d\n",ans);
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 2126ms, 内存消耗: 4848K, 提交时间: 2022-08-26 13:33:35
#include <bits/stdc++.h>
using namespace std;
const int maxn=3005;
int n,m,ans,cnt;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char ch[maxn];
bitset<maxn*4>s[maxn];
struct node{int x,y;};
bool check(int x,int y)
{
if(x<0||x>n+1||y<0||y>m+1) return 0;
if(!s[x][y]) return 0;
return 1;
}
int bfs(int x,int y)
{
int res=0;
s[x].reset(y);
queue<node>q;
q.push({x,y});
while(!q.empty())
{
node u=q.front();q.pop();res++;
for(int i=0;i<4;i++)
{
int nx=u.x+dx[i],ny=u.y+dy[i];
if(check(nx,ny))
{
s[nx].reset(ny);
q.push({nx,ny});
}
}
}
return res;
}
int main()
{
while(~scanf("%d %d",&n,&m)&&n&&m)
{
getchar();
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
for(int j=0;j<m;j++)
{
int x=isdigit(ch[j])?ch[j]-'0':ch[j]-'A'+10;
for(int k=4;k;k--)
{
if(x&1) s[i].set(4*j+k);
else s[i].reset(4*j+k);
x>>=1;
}
}
}
m<<=2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j])
ans=max(ans,bfs(i,j));
printf("%d\n",ans);
}
return 0;
}