QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #135398 | #4432. Jungle Trail | Sommohito# | AC ✓ | 582ms | 148920kb | C++20 | 9.5kb | 2023-08-05 14:45:52 | 2023-08-05 14:45:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const int N=2003;
int n,m;
string s[N];
int dp[N][N][3][3];
int run(int i,int j,int r,int c)
{
if(i==n-1&&j==m-1)
return 1;
if(dp[i][j][r][c]!=-1)
return dp[i][j][r][c];
int ans=0;
//try down
if(i+1<n && s[i+1][j]!='#')
{
if(s[i+1][j]=='.')
{
bool f=run(i+1,j,2,c);
ans|=f;
}
else if(s[i+1][j]=='O')
{
if(c==2)
{
bool f1=run(i+1,j,0,0);
bool f2=run(i+1,j,1,1);
ans|=f1;
ans|=f2;
}
else if(c==1)
{
bool f=run(i+1,j,1,1);
ans|=f;
}
else if(c==0)
{
bool f=run(i+1,j,0,0);
ans|=f;
}
}
else if(s[i+1][j]=='@')
{
if(c==2)
{
bool f1=run(i+1,j,0,1);
bool f2=run(i+1,j,1,0);
ans|=f1;
ans|=f2;
}
else if(c==1)
{
bool f=run(i+1,j,0,1);
ans|=f;
}
else if(c==0)
{
bool f=run(i+1,j,1,0);
ans|=f;
}
}
}
//try right
if(j+1<m && s[i][j+1]!='#')
{
if(s[i][j+1]=='.')
{
bool f=run(i,j+1,r,2);
ans|=f;
}
else if(s[i][j+1]=='O')
{
if(r==2)
{
bool f1=run(i,j+1,0,0);
bool f2=run(i,j+1,1,1);
ans|=f1;
ans|=f2;
}
else if(r==1)
{
bool f=run(i,j+1,1,1);
ans|=f;
}
else if(r==0)
{
bool f=run(i,j+1,0,0);
ans|=f;
}
}
else if(s[i][j+1]=='@')
{
if(r==2)
{
bool f1=run(i,j+1,0,1);
bool f2=run(i,j+1,1,0);
ans|=f1;
ans|=f2;
}
else if(r==1)
{
bool f=run(i,j+1,1,0);
ans|=f;
}
else if(r==0)
{
bool f=run(i,j+1,0,1);
ans|=f;
}
}
}
return dp[i][j][r][c]=ans;
}
string row,col,ans;
void dfs(int i,int j,int r,int c)
{
if(i==n-1&&j==m-1)
return;
//try down
if(i+1<n && s[i+1][j]!='#')
{
if(s[i+1][j]=='.')
{
bool f=run(i+1,j,2,c);
if(f)
{
ans+='D';
dfs(i+1,j,2,c);
return;
}
}
else if(s[i+1][j]=='O')
{
if(c==2)
{
bool f1=run(i+1,j,0,0);
bool f2=run(i+1,j,1,1);
if(f1)
{
ans+='D';
row[i+1]=col[j]='N';
dfs(i+1,j,0,0);
return;
}
if(f2)
{
ans+='D';
row[i+1]=col[j]='T';
dfs(i+1,j,1,1);
return;
}
}
else if(c==1)
{
bool f=run(i+1,j,1,1);
if(f)
{
ans+='D';
row[i+1]=col[j]='T';
dfs(i+1,j,1,1);
return;
}
}
else if(c==0)
{
bool f=run(i+1,j,0,0);
if(f)
{
ans+='D';
row[i+1]=col[j]='N';
dfs(i+1,j,0,0);
return;
}
}
}
else if(s[i+1][j]=='@')
{
if(c==2)
{
bool f1=run(i+1,j,0,1);
bool f2=run(i+1,j,1,0);
if(f1) {
ans+='D';
row[i+1]='N';
col[j]='T';
dfs(i+1,j,0,1);
return;
}
if(f2) {
ans+='D';
row[i+1]='T';
col[j]='N';
dfs(i+1,j,1,0);
return;
}
}
else if(c==1)
{
bool f=run(i+1,j,0,1);
if(f) {
ans+='D';
row[i+1]='N';
col[j]='T';
dfs(i+1,j,0,1);
return;
}
}
else if(c==0)
{
bool f=run(i+1,j,1,0);
if(f) {
ans+='D';
row[i+1]='T';
col[j]='N';
dfs(i+1,j,1,0);
return;
}
}
}
}
//try right
if(j+1<m && s[i][j+1]!='#')
{
if(s[i][j+1]=='.')
{
bool f=run(i,j+1,r,2);
if(f)
{
ans+='P';
dfs(i,j+1,r,2);
return;
}
}
else if(s[i][j+1]=='O')
{
if(r==2)
{
bool f1=run(i,j+1,0,0);
bool f2=run(i,j+1,1,1);
if(f1)
{
ans+='P';
row[i]=col[j+1]='N';
dfs(i,j+1,0,0);
return;
}
if(f2)
{
ans+='P';
row[i]=col[j+1]='T';
dfs(i,j+1,1,1);
return;
}
}
else if(r==1)
{
bool f=run(i,j+1,1,1);
if(f)
{
ans+='P';
row[i]=col[j+1]='T';
dfs(i,j+1,1,1);
return;
}
}
else if(r==0)
{
bool f=run(i,j+1,0,0);
if(f)
{
ans+='P';
row[i]=col[j+1]='N';
dfs(i,j+1,0,0);
return;
}
}
}
else if(s[i][j+1]=='@')
{
if(r==2)
{
bool f1=run(i,j+1,0,1);
bool f2=run(i,j+1,1,0);
if(f1)
{
ans+='P';
row[i]='N';
col[j+1]='T';
dfs(i,j+1,0,1);
return;
}
if(f2)
{
ans+='P';
row[i]='T';
col[j+1]='N';
dfs(i,j+1,1,0);
return;
}
}
else if(r==1)
{
bool f=run(i,j+1,1,0);
if(f)
{
ans+='P';
row[i]='T';
col[j+1]='N';
dfs(i,j+1,1,0);
return;
}
}
else if(r==0)
{
bool f=run(i,j+1,0,1);
if(f)
{
ans+='P';
row[i]='N';
col[j+1]='T';
dfs(i,j+1,0,1);
return;
}
}
}
}
return;
}
void TEST_CASES()
{
cin>>n>>m;
for(int i=0; i<n; i++)
cin>>s[i];
for(int i=0; i<n; i++)
{
memset(dp[i],-1,sizeof dp[i]);
}
row.resize(n);
col.resize(m);
for(int i=0;i<n;i++) row[i]='N';
for(int i=0;i<m;i++) col[i]='N';
ans.clear();
bool f=0;
if(s[0][0]=='.')
{
if(run(0,0,2,2)) {
f=1;
dfs(0,0,2,2);
}
}
else if(s[0][0]=='@')
{
if(run(0,0,1,0)) {
f=1;
row[0]='T';
dfs(0,0,1,0);
}
else if(run(0,0,0,1)) {
f=1;
col[0]='T';
dfs(0,0,0,1);
}
}
else if(s[0][0]=='O')
{
if(run(0,0,0,0)){
f=1;
dfs(0,0,0,0);
}
else if(run(0,0,1,1)) {
f=1;
row[0]=col[0]='T';
dfs(0,0,1,1);
}
}
debug(f);
if(f==0) cout<<"NIE\n";
else
{
cout<<"TAK\n";
cout<<row<<"\n";
cout<<col<<"\n";
cout<<ans<<"\n";
}
return;
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 582ms
memory: 148920kb
input:
486 4 5 ..#.. @@O@@ ##@#O ..@.@ 2 2 OO OO 2 2 @@ @@ 2 2 @@ #@ 2 2 @O #@ 2 2 @@ OO 2 2 O# @O 2 2 @# #@ 2 2 @. .@ 2 2 @# .O 2 2 OO .O 10 10 @O@O#O@@@# OO#@#@@#OO #@#@#O##O@ OO##@@O#@O O##@@#@O#@ OO@OO@@@O@ @O#@#@O#@O @OOOOO@##. O@OOO##O@@ OO@@OOOO#@ 10 10 @@#OOO#O@@ #@@OO@@.O@ #.O@@O#@@O OO@@#O@#O@ .#...
output:
TAK NNTT TTNNN DPPDDPP TAK NN NN DP TAK TT NN DP TAK TT NN PD TAK TN NT PD TAK TN NN DP TAK NT NT DP NIE TAK TN NT DP TAK TN NN DP TAK NN NN DP NIE TAK TTNNTTTTNT NNTTNNTTNN PDDDPPDDDDPPDDPPPP TAK NTTTNTNNNN NTTTNTNTTN DDDDDPDDDPPPPPDPPP TAK NNNTNTTTNT NNTTTTTNNT DDDPPDPDDDDDPPPPPP TAK NNNTNNNTNT NN...
result:
ok ac (486 test cases)
Extra Test:
score: 0
Extra Test Passed