QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #135365 | #4432. Jungle Trail | Sommohito# | WA | 581ms | 148824kb | C++20 | 9.5kb | 2023-08-05 14:03:24 | 2023-08-05 14:03:28 |
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,'N');
col.resize(m,'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;
row[0]=col[0]='N';
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;
}
详细
Test #1:
score: 0
Wrong Answer
time: 581ms
memory: 148824kb
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 NTNTNTTTNT NNTTTTTNNT DDDPPDPDDDDDPPPPPP TAK NTNTNNNTNT NN...
result:
wrong answer you dead (test case 114)