QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #673231 | #4434. Lemurs | kirco | AC ✓ | 976ms | 20548kb | C++23 | 1.8kb | 2024-10-24 21:15:31 | 2024-10-24 21:15:32 |
Judging History
answer
#include <bits/stdc++.h>
#define iosy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 0x3f3f3f3f//十六进制约等于1061109567,1e9多不超int范围
using namespace std;
//O(n*m)
const int N = 1005;
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int n,m,k;
vector<vector<char>> mp(N,vector<char>(N));
int d1[N][N],d2[N][N];
bool pd(int x,int y){//判断是否出图
if(x<1||x>n||y<1||y>m)return false;
return true;
}
void bfs1(){
queue<pair<int,int>> q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d1[i][j]=inf;
if(mp[i][j]=='.'){
q.push({i,j});
d1[i][j]=0;
}
}
}
while(!q.empty()){
auto [x,y]=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(pd(nx,ny)&&d1[nx][ny]==inf){
d1[nx][ny]=d1[x][y]+1;
q.push({nx,ny});
}
}
}
}
void bfs2(){
queue<pair<int,int>> q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d2[i][j]=inf;
if(mp[i][j]=='x'&&d1[i][j]>k){
q.push({i,j});
d2[i][j]=0;
}//大于k的点'x'一定都可作为巢穴
}
}
while(!q.empty()){
auto [x,y]=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(pd(nx,ny)&&d2[nx][ny]==inf){//ctrl+c/v容易出问题,不仔细检查是sb
d2[nx][ny]=d2[x][y]+1;
q.push({nx,ny});
}
}
}
}
void solve(){
cin>>n>>m>>k;//觅食范围是一个菱形
for(int i=1;i<=n;i++){
string s;cin>>s;s=" "+s;
for(int j=1;j<=m;j++){
mp[i][j]=s[j];
}
}
bfs1();
bfs2();
//假设可以
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='x'&&d2[i][j]>k){
//cout<<"i="<<i<<"j="<<j<<"\n";
return cout<<"NIE\n",void();
}
}
}
cout<<"TAK\n";
}
signed main()
{
iosy;
int _t=1;
cin>>_t;
while(_t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 17ms
memory: 12732kb
input:
4000 1 1 1 . 1 1 1 x 1 1 1000 . 1 1 1000 x 1 1000 4 ..........................................xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx....xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
TAK TAK TAK TAK TAK NIE NIE TAK NIE TAK NIE NIE TAK TAK NIE TAK TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE TAK TAK TAK NIE NIE NIE TAK TAK NIE NIE TAK NIE NIE NIE TAK NIE NIE NIE TAK NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE NIE TAK TAK ...
result:
ok 4000 lines
Test #2:
score: 0
Accepted
time: 976ms
memory: 20548kb
input:
36 1000 1000 2 ....xxxx..............xxxxxx..........xx..xxxx......xxxxxxxxxxx.........xxxxxxxxxx...xxxxxx....xxxxxx.......xxxxxx....xxxxxx......................................xx.............xxxxxxxxx......xxxxxxx................xxxxxx..xxxxxx....xxxxxx..............xxxxxxxxxxxxxxxxxxxxxxxxxxxx...x...
output:
TAK NIE NIE TAK TAK NIE TAK NIE NIE TAK TAK NIE NIE NIE NIE TAK NIE TAK TAK TAK TAK NIE TAK NIE NIE TAK NIE TAK NIE NIE NIE TAK TAK NIE NIE NIE
result:
ok 36 lines
Test #3:
score: 0
Accepted
time: 945ms
memory: 20192kb
input:
41 1000 1000 999 .xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
NIE TAK TAK NIE TAK TAK TAK NIE TAK NIE TAK TAK TAK NIE TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE TAK NIE NIE NIE NIE TAK TAK NIE NIE NIE TAK NIE NIE NIE
result:
ok 41 lines
Extra Test:
score: 0
Extra Test Passed