奇怪的思路,过不了样例,球大佬帮帮蒟蒻(有详细注释)
  • 板块P1189 SEARCH
  • 楼主JoeBiden2020
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/10/5 23:20
  • 上次更新2023/11/4 04:39:55
查看原帖
奇怪的思路,过不了样例,球大佬帮帮蒟蒻(有详细注释)
432183
JoeBiden2020楼主2021/10/5 23:20
#include<bits/stdc++.h>
using namespace std;
int r,c,n;
bool temp[51][51];//temp:是否是当前轮新增的  
char a[51][51];//a:输入&答案输出 
void work(int way){
	for(register int i=1;i<=r;i++){
		for(register int j=1;j<=c;j++){//O(rc)枚举每个方格 
			if(a[i][j]=='*'&&!temp[i][j]){//如果该方格为 * 且非新增方格,则按方向拓展 
				a[i][j]='.';//自身变为 . 
				if(way==1){//北 
					int len=1;
					while(j+len<=r&&a[i][j+len]!='X'){//不断枚举可能的行动方案,将其设为 * ,直到遇到障碍或越界为止。 
						a[i][j+len]='*';
						temp[i][j+len]=1;//设为新增,防止循环枚举它时认为它为当前阶段的可能开始点 
						len++;
					}
				}
				if(way==2){//南 
					int len=1;
					while(j-len>0&&a[i][j-len]!='X'){
						a[i][j-len]='*';
						temp[i][j-len]=1;
						len++;
					}
				}
				if(way==3){//东 
					int len=1;
					while(i+len<=c&&a[i+len][j]!='X'){
						a[i+len][j]='*';
						temp[i+len][j]=1;
						len++;
					}
				}
				if(way==4){//西 
					int len=1;
					while(i-len>0&&a[i-len][j]!='X'){
						a[i-len][j]='*';
						temp[i-len][j]=1;
						len++;
					}
				}
			}
		}
	}
	memset(temp,0,sizeof(temp));//重置 
}
int main(){
	cin>>r>>c;
	for(register int i=1;i<=r;i++){
		for(register int j=1;j<=c;j++){
			cin>>a[i][j];//输入 
		}
	}
	cin>>n;
	for(register int i=1;i<=n;i++){
		string tt;
		cin>>tt;
		if(tt=="NORTH")work(1);
		if(tt=="SOUTH")work(2);
		if(tt=="EAST")work(3);//操作 总复杂度 O(nrc)? 
		if(tt=="WEST")work(4);
//		cout<<i<<":\n";
//		for(register int i=1;i<=r;i++){
//			for(register int j=1;j<=c;j++){
//				cout<<a[i][j];
//			}
//			cout<<"\n";
//		}
	}
	for(register int i=1;i<=r;i++){
		for(register int j=1;j<=c;j++){
			cout<<a[i][j];
		}
		cout<<"\n";
	}
} 
2021/10/5 23:20
加载中...