HDu 1175連見(DFS+枝切り)
しきりに見る
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25111 Accepted Submission(s): 6211
Problem Description
「連見」は多くの人が遊んだことがあると信じています.遊んだことがなくても大丈夫です.次はゲームのルールを紹介します.碁盤の中に、たくさんの駒が置いてあります.もしある2つの同じ駒が、1本の線でつながっていて(この線は他の駒を通ることができません)、しかも線の転換回数が2回を超えなければ、この2つの駒は碁盤の上で消すことができます.申し訳ありませんが、私は以前游んだことがないので、友达の意見を聞いて、外から迂回することはできませんが、実はこれは間違っています.今はすでに大きな災いになって、間違いを間違えるしかなくて、線は外周から迂回することができません.
プレイヤーのマウスは前後して2つの駒をクリックして、彼らを消そうとして、それからゲームのバックグラウンドはこの2つの格子が消せるかどうかを判断します.今あなたの任務はこのバックグラウンドプログラムを書くことです.
Input
入力データは複数組あります.各グループのデータの第1行には2つの正の整数n,m(0注意:質問の間には前後関係がなく、現在の状態に対応しています.
Output
各入力データのセットは、1行の出力に対応します.消去できる場合は「YES」、できない場合は「NO」を出力します.
Sample Input
Sample Output
Author
lwg
Recommend
We have carefully selected several similar problems for you: 1180 1072 1026 1240 1253
Statistic | Submit | Discuss | Note
先日この問題をしたとき、主に意味が理解できなかった.何度もwaを流した.曲がるのは2つの数の隙間を歩いているのかと思ったら...
腹立たしいですね.
今日やっと数字の上を歩いていることに気づいた.しかも0.しか歩けない.つまり駒のない場所を歩くしかない.
8642 ms危険です.の
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 25111 Accepted Submission(s): 6211
Problem Description
「連見」は多くの人が遊んだことがあると信じています.遊んだことがなくても大丈夫です.次はゲームのルールを紹介します.碁盤の中に、たくさんの駒が置いてあります.もしある2つの同じ駒が、1本の線でつながっていて(この線は他の駒を通ることができません)、しかも線の転換回数が2回を超えなければ、この2つの駒は碁盤の上で消すことができます.申し訳ありませんが、私は以前游んだことがないので、友达の意見を聞いて、外から迂回することはできませんが、実はこれは間違っています.今はすでに大きな災いになって、間違いを間違えるしかなくて、線は外周から迂回することができません.
プレイヤーのマウスは前後して2つの駒をクリックして、彼らを消そうとして、それからゲームのバックグラウンドはこの2つの格子が消せるかどうかを判断します.今あなたの任務はこのバックグラウンドプログラムを書くことです.
Input
入力データは複数組あります.各グループのデータの第1行には2つの正の整数n,m(0
Output
各入力データのセットは、1行の出力に対応します.消去できる場合は「YES」、できない場合は「NO」を出力します.
Sample Input
3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0
Sample Output
YES
NO
NO
NO
NO
YES
Author
lwg
Recommend
We have carefully selected several similar problems for you: 1180 1072 1026 1240 1253
Statistic | Submit | Discuss | Note
先日この問題をしたとき、主に意味が理解できなかった.何度もwaを流した.曲がるのは2つの数の隙間を歩いているのかと思ったら...
腹立たしいですね.
今日やっと数字の上を歩いていることに気づいた.しかも0.しか歩けない.つまり駒のない場所を歩くしかない.
8642 ms危険です.の
#include <stdio.h>
#include <string.h>
int flag,st1,st2,ed1,ed2,m,n;
int dir[4][2]={1,0,-1,0,0,1,0,-1},map[1005][1005],vis[1005][1005];
bool no(int x,int y)
{
if(x<0||y<0||x==m||y==n)
return true;
else
return false;
}
void dfs(int x,int y,int cor,int cnt)
{
if(cnt>2||flag||x<0||x==m||y<0||y==n)
return ;
if(x==ed1&&y==ed2)
{
flag=1;
return ;
}
if(map[x][y]!=0&&cor!=-1) return ;
for(int i=0;i<4;i++)
{
int temp_x=x+dir[i][0];
int temp_y=y+dir[i][1];
if(vis[temp_x][temp_y]||no(temp_x,temp_y))
continue;
vis[temp_x][temp_y]=1;
if(cor!=i&&cor!=-1)
cnt++;
dfs(temp_x,temp_y,i,cnt);
if(cor!=i&&cor!=-1)
cnt--;
vis[temp_x][temp_y]=0;
}
}
int main()
{
while(scanf("%d %d",&m,&n)!=EOF)
{
if(m==0&&n==0)
break;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&map[i][j]);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d %d %d %d",&st1,&st2,&ed1,&ed2);
st1--,st2--,ed1--,ed2--;
if(st1<0||st2<0||ed1<0||ed2<0||st1>=m||ed1>=m||st2>=n||ed2>=n)
{
printf("NO
");
continue;
}
if(map[st1][st2]!=map[ed1][ed2]||!map[st1][st2]||!map[ed1][ed2])
{
printf("NO
");
continue;
}
memset(vis,0,sizeof(vis));
flag=0;
vis[st1][st2]=1;
dfs(st1,st2,-1,0);
if(flag)
printf("YES
");
else
printf("NO
");
}
}
return 0;
}