QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #672810 | #4434. Lemurs | kirco | TL | 451ms | 6604kb | C++23 | 1.8kb | 2024-10-24 19:15:16 | 2024-10-24 19:15:17 |
Judging History
answer
#include <bits/stdc++.h>
#define iosy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
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));
bool use[N][N];
char ans[N][N];
bool pd(int x,int y){//判断是否出图
if(x<1||x>n||y<1||y>m)return false;
return true;
}
void bfs1(int x,int y){
queue<pair<int,int>> q;
vector<vector<bool>> vis(n+1,vector<bool>(m+1,false));
q.push({x,y});vis[x][y]=true;
while(!q.empty()){
auto& [tx,ty]=q.front();
q.pop();
use[tx][ty]=1;
for(int i=0;i<4;i++){
int tnx=tx+dx[i],tny=ty+dy[i];
if(pd(tnx,tny)&&abs(tnx-x)+abs(tny-y)<=k&&!vis[tnx][tny]){
vis[tnx][tny]=1;
q.push({tnx,tny});
}
}
}
}
void bfs2(int x,int y){
queue<pair<int,int>> q;
vector<vector<bool>> vis(n+1,vector<bool>(m+1,false));
q.push({x,y});vis[x][y]=true;
while(!q.empty()){
auto& [tx,ty]=q.front();
q.pop();
ans[tx][ty]='x';
for(int i=0;i<4;i++){
int tnx=tx+dx[i],tny=ty+dy[i];
if(pd(tnx,tny)&&abs(tnx-x)+abs(tny-y)<=k&&!vis[tnx][tny]){
vis[tnx][tny]=1;
q.push({tnx,tny});
}
}
}
}
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];
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]=='.')bfs1(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!use[i][j])bfs2(i,j);
bool ok=1;//假设可以
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='x'&&ans[i][j]!='x'){
ok=0;
break;
}
}
}
cout<<(ok? "TAK\n":"NIE\n");
//清空多测
memset(use,0,sizeof(use));
memset(ans,'B',sizeof(ans));
}
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: 451ms
memory: 6604kb
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: -100
Time Limit Exceeded
input:
36 1000 1000 2 ....xxxx..............xxxxxx..........xx..xxxx......xxxxxxxxxxx.........xxxxxxxxxx...xxxxxx....xxxxxx.......xxxxxx....xxxxxx......................................xx.............xxxxxxxxx......xxxxxxx................xxxxxx..xxxxxx....xxxxxx..............xxxxxxxxxxxxxxxxxxxxxxxxxxxx...x...