QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #673188 | #4434. Lemurs | kirco | TL | 451ms | 6616kb | C++23 | 1.8kb | 2024-10-24 20:57:38 | 2024-10-24 20:58:05 |
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(){
//清空多测
memset(use,0,sizeof(use));
memset(ans,'B',sizeof(ans));
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);
//假设可以
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='x'&&ans[i][j]!='x'){
return cout<<"NIE\n",void();
}
}
}
cout<<"TAK\n";
}
signed main()
{
iosy;
int _t=1;
cin>>_t;
while(_t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 451ms
memory: 6616kb
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...